881.Boats to Save People
===

###### tags: `Medium`,`Array`,`Two Pointers`,`Greedy`,`Sorting`

[881. Boats to Save People](https://leetcode.com/problems/boats-to-save-people/)

### 題目描述

You are given an array `people` where `people[i]` is the weight of the i^th^ person, and an **infinite number of boats** where each boat can carry a maximum weight of `limit`. Each boat carries at most two 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*.

### 範例

**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)

**Constraints**:

* 1 <= `people.length` <= 5 * 10^4^
* 1 <= `people[i]` <= `limit` <= 3 * 10^4^

### 解答
#### C++

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int ans = 0, l = 0, r = people.size() - 1;
        sort(people.begin(), people.end());
        while (l <= r) {
            if (people[l] + people[r] <= limit) {
                l++;
            }
            ans++;
            r--;
        }
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Mon, Apr 3, 2023]

#### Python

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        ans, l, r = 0, 0, len(people)-1
        people.sort()
        while l <= r:
            if people[l] + people[r] <= limit:
                l += 1
            ans += 1
            r -= 1
        return ans

> [name=Yen-Chi Chen][time=Mon, Apr 3, 2023]

#### Javascript

function numRescueBoats(people, limit) {
  people.sort((a, b) => b - a);
  let boats = 0;
  let right = people.length - 1;

  for (let left = 0; left <= right; left++) {
    if (people[left] + people[right] <= limit) {
      boats++;
      right--;
    } else {
      boats++;
    }
  }

  return boats;
}

> [name=Marsgoat][time=Apr 12, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)