Leet Code Daily 2024-05-04 - Boats to Save People
Solution
- First, sort all
people in incresing order.
- Let's say
people[i..j] are the people which are not shipped yet.
- There are several cases:
i == j, then we only need last boat.people[i] + people[j] <= limit, then we carry both of them.- otherwise,
people[j] must be shipped alone.
Code
● ● ●c++class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
sort(people.begin(), people.end());
int ans = 0;
for (int i = 0, j = people.size() - 1; i <= j; ) {
if (i == j) {
ans++;
i++;
} else if (people[i] + people[j] <= limit) {
i++;
j--;
ans++;
} else {
j--;
ans++;
}
}
return ans;
}
};