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 = 3Output:1Explanation:1 boat (1, 2)

**Example 2:**

Input:people = [3,2,2,1], limit = 3Output:3Explanation: 3 boats (1, 2), (2) and (3)

**Example 3:**

Input:people = [3,5,3,4], limit = 5Output:4Explanation: 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;
}
};
```

Java

```
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;
}
}
```