881.Boats to Save People¶
Tags: Medium
Greedy
Links: https://leetcode.com/problems/boats-to-save-people/submissions/
The i
-th person has weight people[i]
, and each boat can carry a maximum weight of limit
.
Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit
.
Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)
Example 1:
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)
Example 2:
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)
Example 3:
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)
Note:
1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = people.size();
int cnt = 0;
sort(people.begin(), people.end());
int start = 0, end = n - 1;
while (start <= end) {
if (people[start] + people[end] > limit) {
++cnt; --end;
}
else {
++cnt; ++start; --end;
}
}
return cnt;
}
};
很典型的贪心问题之乘船问题,胖的和瘦的乘坐一条船。