[Programmers] Lifeboat

https://programmers.co.kr/learn/courses/30/lessons/42885

Solution

Read the constraints carefully. I wasted a lot of time by missing the condition that only 2 people can ride a boat at once.

When each boat holds at most 2 people, the most efficient strategy is to pair the heaviest person with the lightest. Sort the people array, then shrink indices from both ends. As long as you properly handle the case where a heavy person rides alone, ascending or descending sort both work.

Code

https://github.com/naem1023/codingTest/blob/master/greedy/pg-30-42885.py

1
def solution(people, limit):
2
    cnt  = 0
3
    people.sort()
4

5
    start, end = 0, len(people) - 1
6

7
    while start <= end:
8
        cnt += 1
9
        if people[start] + people[end] <= limit:
10
            start += 1
11
        end -= 1
12

13
    return cnt