881. 救生艇
贪心,时间复杂度:\(O(nlogn)\)
先排序,然后每次尝试将当前质量最大的人和质量最小的人放一块。
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
int res = 0, n = people.size();
sort(people.begin(), people.end());
for(int i = 0, j = n - 1; i <= j; --j){
if(people[i] + people[j] <= limit)i++;
res ++;
}
return res;
}
};