Each boat holds two people under a weight limit. Sort, then pair the heaviest with the lightest when they fit; otherwise the heaviest rides alone.
▼The problem
LeetCode 881 (Medium). people[i] is a person's weight. Each boat carries at most two people at once, as long as their total weight is at most limit (nobody weighs more than limit). Return the minimum number of boats that carry everyone.
Examples (LeetCode's): people = [1,2], limit = 3 → 1; [3,2,2,1], limit = 3 → 3 (boats (3), (1,2), (2)); [3,5,3,4], limit = 5 → 4 (the lightest two already weigh 6).
The solution
def num_rescue_boats(people, limit):
people.sort()
left, right = 0, len(people) - 1
boats = 0
while left <= right:
if people[left] + people[right] <= limit:
left += 1 # the lightest rides along
right -= 1 # the heaviest always boards
boats += 1
return boatsTranscript
Boats to Save People. A flood, and people wait on a pier, each with a weight. A boat carries at most two people, with total weight up to the limit. What's the fewest boats that save everyone?
Weights one and two, limit three: one boat carries both. Three, two, two, one, limit three: three boats. Three, five, three, four, limit five: no two fit together, so four boats.
Trying every pairing is exponential. A quick greedy without sorting fails too. Take two, one, three, two, limit four, and pair each person with the first who fits. Two takes one, then three and two can't share. Three boats, but two will do.
The key idea: sort, then look at the heaviest person. They always need a boat. If anyone can share it, the lightest can. So when the lightest fits, they ride together. Otherwise the heaviest rides alone.
In code, sort and put a pointer at each end. While left hasn't passed right, if the lightest and heaviest fit, left steps in. Right always steps in, and we count a boat.
Now three, two, two, one, limit three, sorted to one, two, two, three. One plus three is four, too heavy: three rides alone. One plus two is three: they share boat two. The last two rides alone: boat three. Three boats.
Sorting takes n log n time, then one pass as the pointers meet. Beyond the sort, two pointers and a count: constant space.
Sort, board the heaviest, add the lightest if they fit. That's Boats to Save People.