unreasonably effective

link

Blind alleys

1. The min and max required boat count must be in . Given a boat count, if in a single scan we could tell if all people can be packed we could use a binary search in that range. But, due to the weight and 2-person per boat restrictions a single sequential scan is not sufficient to be able to tell if the boat count is adequate. Because, for a person, there might be a better choice far out.

What works

The best pairing for the heaviest person is the lightest person. If combining the weight of the lightest person does not work, the heaviest person must ride alone. So, we sort the weights and on each iteration try pairing the heaviest with the lightest.

Time: , space: .

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()

        boat_count = 0
        lo, hi = 0, len(people)-1
        while lo <= hi:
            boat_count += 1
            
            combined_weight = people[lo] + people[hi]
            if combined_weight <= limit: # can take both persons
                lo += 1
                hi -= 1
            else: # take the heavier
                hi -= 1
        
        return boat_count