Minimum Rescue Boats Needed Under a Weight Limit
Implement minimumRescueBoats
Every person in
people needs to be ferried across, and every boat can carry at most two people at once as long as their combined weight doesn't exceed limit. Every person's own weight is guaranteed to fit within the limit on its own, so nobody is ever stranded. Find the fewest boat trips needed to get everyone across.
A greedy pairing works well once the weights are sorted: try to pair the heaviest person still waiting with the lightest person still waiting. If they fit together, send both on one trip; if not, the heaviest has to go alone, since nobody lighter would fit with them either.
Example 1:
Input: people = [4,6], limit = 10
Output: 1
Example 2:
Input: people = [7,3,5,2], limit = 8
Output: 3
Example 3:
Input: people = [9,9,9], limit = 9
Output: 3
+ 5 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ people.length ≤ 5×10⁴ - ●
1 ≤ people[i] ≤ limit ≤ 3×10⁴ - ●
Every person's weight is at most limit, so everyone can always fit on some boat alone
people =
[4, 6]
limit =
10