#881
Boats to Save People
Medium Sort + opposite ends
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Each boat carries at most two people and has a weight limit. Return the minimum number of boats to carry everyone.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: boats carry at most 2 people under a weight limit; fewest boats?
Why this works: the heaviest person must go now. The only useful partner is the lightest person; if even they don't fit, nobody does.
Example: [3, 2, 2, 1], limit 3 → sorted [1, 2, 2, 3]
3 + 1 = 4 > 3 → 3 alone (boat 1)2 + 1 = 3 ✓ (boat 2)2 alone (boat 3) → 3 boats
✦Hints open one at a time
Sort by weight.
The heaviest person goes in a boat now. Can the lightest person squeeze in too?
↗Approach
Sort, then pointers at the lightest and heaviest. The heaviest always boards; the lightest joins if the pair fits. Each step uses one boat.
</>Solution (Java)
import java.util.*;
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int l = 0, r = people.length - 1, boats = 0;
while (l <= r) {
if (people[l] + people[r] <= limit) l++; // lightest rides along
r--; // heaviest always leaves
boats++;
}
return boats;
}
}!Common mistake
Pairing the heaviest with the heaviest who fits — the lightest is always the safest partner.
Complexity
- Time: O(n log n).
- Space: O(log n) for sorting.
