881. Boats to Save People

解題時剛好在聽這首，隨意分享一下 OneRepublic - Counting Stars (One Night in Malibu)

題目敘述

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

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

/**
 * @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

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

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

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

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

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