Boats to Save People
Problem
Each boat carries at most two people, as long as their combined weight is within limit. Given the weights people and the limit, return the minimum number of boats needed to carry everyone.
people = [3, 2, 2, 1], limit = 33def num_rescue_boats(people, limit):
people.sort()
lo, hi, boats = 0, len(people) - 1, 0
while lo <= hi:
if people[lo] + people[hi] <= limit:
lo += 1
hi -= 1
boats += 1
return boatsfunction numRescueBoats(people, limit) {
people.sort((a, b) => a - b);
let lo = 0, hi = people.length - 1, boats = 0;
while (lo <= hi) {
if (people[lo] + people[hi] <= limit) lo++;
hi--;
boats++;
}
return boats;
}int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int lo = 0, hi = people.length - 1, boats = 0;
while (lo <= hi) {
if (people[lo] + people[hi] <= limit) lo++;
hi--;
boats++;
}
return boats;
}int numRescueBoats(vector<int>& people, int limit) {
sort(people.begin(), people.end());
int lo = 0, hi = people.size() - 1, boats = 0;
while (lo <= hi) {
if (people[lo] + people[hi] <= limit) lo++;
hi--;
boats++;
}
return boats;
}Explanation
Each boat holds at most two people within a weight limit, and we want the fewest boats. The greedy insight: the heaviest remaining person must sail anyway, so we try to pair them with the lightest remaining person.
After sorting weights ascending, a low pointer lo marks the lightest and a high pointer hi the heaviest. If people[lo] + people[hi] <= limit they share a boat, so we advance lo. Either way the heaviest is now seated, so we always move hi down and add one boat.
This is optimal because if the lightest person cannot share with the heaviest, they cannot share with anyone heavier either, so the heaviest gets a boat alone with no regret.
Example: sorted [1, 2, 2, 3], limit 3. 1 + 3 = 4 > 3, so 3 goes alone. Then 1 + 2 = 3 ≤ 3, they pair. The last 2 takes its own boat → 3 boats total.
Each step seats at least one person and counts one boat, so the pointers meet quickly and the count is the minimum.