# LeetCode Solution, Medium, 881. Boats to Save People

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

解題時剛好在聽這首，隨意分享一下 [OneRepublic - Counting Stars (One Night in Malibu)](https://youtu.be/A18ciouGCS4)

## 題目敘述

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`

### 題目翻譯

有一個陣列參數 `people`，每個元素代表這個人的體重。現在有無限多個船，每個船只能載兩個人，而每個船的載重量是 `limit`，要找出最少需要多少船才能載完所有人。

## 解法解析

這題是將 `people` 依照數字排序，所以排完後會類似如此的`[1, 2, 3...9, 10]`。因為需要盡可能少的船隻，所以最佳的狀況是**最重**的跟**最輕**的搭配，所以用 `i`和 `j` 分別從開頭和結尾的地方開始做搭配。

額外思考：如果今天每個船隻的載重量的不同的話怎麼解呢？

自己想到的方法是對船隻也依照載重量排序，然後從載重量最重的來找可以載的人。載的人則從最重的人的開始找。

### 解法範例

#### Go

```go
func numRescueBoats(people []int, limit int) int {
	sort.Ints(people)
	var ans int
	for i, j := 0, len(people)-1; i <= j; {
		ans++
		if people[i]+people[j] <= limit {
			i++
		}
		j--
	}
	return ans
}
```

#### JavaScript

```javascript
/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function (people, limit) {
    people.sort((a, b) => a - b);
    let i = 0,
        j = people.length - 1,
        ans = 0;
    while (i <= j) {
        ans++;
        if (people[i] + people[j] <= limit) {
            i++;
        }
        j--;
    }
    return ans;
};
```

#### Kotlin

```kotlin
class Solution {
    fun numRescueBoats(people: IntArray, limit: Int): Int {
        people.sort()
        var i = 0
        var j = people.size - 1
        var ans = 0
        while (i <= j) {
            ans++
            if (people[i] + people[j] <= limit) {
                i++
            }
            j--
        }
        return ans
    }
}
```

#### PHP

```php
class Solution
{
    /**
     * @param Integer[] $people
     * @param Integer $limit
     * @return Integer
     */
    function numRescueBoats($people, $limit)
    {
        sort($people);
        $i = 0;
        $j = count($people) - 1;
        $ans = 0;
        while ($i <= $j) {
            $ans++;
            if ($people[$i] + $people[$j] <= $limit) {
                $i++;
            }
            $j--;
        }
        return $ans;
    }
}
```

#### Python

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

#### Rust

```rust
impl Solution {
    pub fn num_rescue_boats(people: Vec<i32>, limit: i32) -> i32 {
        let mut people = people;
        people.sort_unstable();
        let (mut i, mut j) = (0, people.len() - 1);
        let mut ans = 0;
        while i < j {
            if people[i] + people[j] <= limit {
                i += 1;
            }
            j -= 1;
            ans += 1;
        }
        ans + if i == j { 1 } else { 0 }
    }
}
```

#### Swift

```swift
class Solution {
    func numRescueBoats(_ people: [Int], _ limit: Int) -> Int {
        var people = people.sorted()
        var ans = 0
        var i = 0
        var j = people.count - 1
        while i <= j {
            ans += 1
            if people[i] + people[j] <= limit {
                i += 1
            }
            j -= 1
        }
        return ans
    }
}
```