Boats to Save People
There are people in a river and a limited number of boats to save them. Each boat can only hold a certain number of people. Given the weights of the people and the capacity of the boats, determine the minimum number of boats required to save everyone.
Constraints:
- 1 <= people.length <= 10^5
- 1 <= limit <= 10^5
- people[i] <= limit
Examples:
Input: [1,2,2,3], 3
Output: 3
Explanation: The first boat can carry the person with weight 1, the second boat can carry the two people with weights 2, and the third boat can carry the person with weight 3.
Solutions
Two Pointers
The solution uses a two-pointer approach. The people are first sorted in ascending order. Then, two pointers are used to traverse the array from both ends. If the sum of the weights of the people at the current positions of the two pointers is less than or equal to the capacity of the boat, the person with the lighter weight is moved to the next position. The number of boats is incremented, and the person with the heavier weight is moved to the previous position. This process continues until all people have been rescued.
int numRescueBoats(vector<int>& people, int limit) {
sort(people.begin(), people.end());
int light = 0, heavy = people.size() - 1, boats = 0;
while (light <= heavy) {
if (people[light] + people[heavy] <= limit) light++;
boats++;
heavy--;
}
return boats;
}Follow-up:
What if the capacity of the boats is not fixed?
