Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/881.html
881. Boats to Save People (Medium)
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
Companies:
Google
Related Topics:
Two Pointers, Greedy
Solution 1. Greedy
// OJ: https://leetcode.com/problems/boats-to-save-people/
// Time: O(NlogD) where N is to total number of people
// and D is the distinct count of weights.
// Space: O(D)
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
map<int, int, greater<int>> m;
for (int w : people) m[w]++;
int ans = 0;
while (m.size()) {
int w = limit, cnt = 0;
while (w > 0 && cnt < 2) {
auto it = m.lower_bound(w);
if (it == m.end()) break;
w -= it->first;
if (--it->second == 0) m.erase(it->first);
++cnt;
}
++ans;
}
return ans;
}
};
Solution 2. Greedy + Two Pointers
For the lightest person a
, if a
can pair with the heaviest person b
, let a
do so.
If not, then the heaviest person b
can’t pair with any one, let b
go alone.
// OJ: https://leetcode.com/problems/boats-to-save-people/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int numRescueBoats(vector<int>& A, int limit) {
sort(begin(A), end(A));
int i = 0, j = A.size() - 1, ans = 0;
while (i <= j) {
++ans;
if (A[i] + A[j] <= limit) ++i;
--j;
}
return ans;
}
};
-
class Solution { public int numRescueBoats(int[] people, int limit) { int boatsCount = 0; Arrays.sort(people); int low = 0, high = people.length - 1; while (low <= high) { if (people[low] + people[high] <= limit) low++; high--; boatsCount++; } return boatsCount; } } ############ class Solution { public int numRescueBoats(int[] people, int limit) { Arrays.sort(people); int ans = 0; for (int i = 0, j = people.length - 1; i <= j; --j) { if (people[i] + people[j] <= limit) { ++i; } ++ans; } return ans; } }
-
// OJ: https://leetcode.com/problems/boats-to-save-people/ // Time: O(NlogD) where N is to total number of people // and D is the distinct count of weights. // Space: O(D) class Solution { public: int numRescueBoats(vector<int>& people, int limit) { map<int, int, greater<int>> m; for (int w : people) m[w]++; int ans = 0; while (m.size()) { int w = limit, cnt = 0; while (w > 0 && cnt < 2) { auto it = m.lower_bound(w); if (it == m.end()) break; w -= it->first; if (--it->second == 0) m.erase(it->first); ++cnt; } ++ans; } return ans; } };
-
class Solution: def numRescueBoats(self, people: List[int], limit: int) -> int: people.sort() ans = 0 i, j = 0, len(people) - 1 while i <= j: if people[i] + people[j] <= limit: i += 1 j -= 1 ans += 1 return ans ############ class Solution(object): def numRescueBoats(self, people, limit): """ :type people: List[int] :type limit: int :rtype: int """ people.sort() res = 0 hi, lo = len(people) - 1, 0 while hi >= lo: if people[hi] + people[lo] <= limit: lo += 1 hi -= 1 res += 1 return res
-
func numRescueBoats(people []int, limit int) int { sort.Ints(people) ans := 0 for i, j := 0, len(people)-1; i <= j; j-- { if people[i]+people[j] <= limit { i++ } ans++ } return ans }