The array people holds the weight of each person, and every boat can carry at most limit weight and at most two people at a time. No single person is heavier than limit. Return the minimum number of boats needed to carry everyone.
- 1 <= people.length <= 5 * 10^4
- 1 <= people[i] <= limit <= 3 * 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying all pairings is exponential. Think greedily about the heaviest person: they need a boat no matter what. If even the lightest person cannot share with them, nobody can, so they go alone. If the lightest fits, pairing them is never worse than any other choice, because the lightest person is the easiest to place. After sorting, two pointers apply this rule from both ends in one pass.
Algorithm
- Sort
people. - Set
l = 0,r = n - 1,boats = 0. - While
l <= r: ifpeople[l] + people[r] <= limit, movelright (the lightest rides too). - Always move
rleft and add one boat. - Return
boats.
O(n log n) for sortingSpace: O(1) extra (sorting aside)class Solution: def numRescueBoats(self, people: List[int], limit: int) -> int: people.sort() l, r = 0, len(people) - 1 boats = 0 while l <= r: if people[l] + people[r] <= limit: l += 1 # lightest shares with heaviest r -= 1 # heaviest always leaves boats += 1 return boats