🔗 🟡 881. Boats to Save People 1530

tags: `Weekly Contest 96` `貪心(Greedy)` `排序(Sorting)` `雙指標(Two Pointers)`

題意

給定一個陣列 $people$ ，其中 $people[i]$ 是第 $i$ 個人的重量，還有無限數量的船，每艘船能承載的最大重量是 $limit$ 。

每艘船最多同時載兩個人，前提是這兩個人的總重量不超過 $limit$ 。

返回承載所有人所需要的最少船數。

思路：貪心(Greedy) + 排序(Sorting) + 雙指標(Two Pointers)

首先確定思路，對於某個體重為 $x$ 的人，我們希望找到另一個體重為 $y$ 的人，使得 $x + y \leq \text{limit}$ ，這樣我們就可以將這兩個人放在同一艘船上。在固定 $x$ 的情況下，為了使船的數量最少，我們希望 $y$ 的體重越大越好，這樣才能保證在滿足限重的情況下，盡可能多地載人。

基於這個貪心(Greedy) 思路，可以將所有人按照體重進行排序，然後使用雙指針的方法，一個指針 $i$ 指向最輕的人，另一個指針 $j$ 指向最重的人。

如果這兩個人的重量和小於或等於 $limit$ ，我們可以將他們安排在同一艘船上，然後移動兩個指針， $i$ 增加 $1$ ， $j$ 減少 $1$ 。
如果這兩個人的重量和大於 $limit$ ，我們只能將較重的那個人單獨安排在一艘船上，然後只移動 $j$ 指針， $j$ 減少 $1$ 。

無論哪種情況，每次迭代後，我們都需要增加船的數量。最終，當 $i > j$ 時，表示已經處理完所有人，我們便找到了所需的最少船數。

複雜度分析

時間複雜度：排序需要 $O(n \log n)$ 的時間，雙指針掃描需要 $O(n)$ 的時間，因此總時間複雜度為 $O(n \log n)$ 。
空間複雜度：排序過程所需的空間是 $O(\log n)$ 。

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        ans = 0
        people.sort()
        i, j = 0, len(people) - 1
        while i <= j:
            if people[i] + people[j] > limit: # 只能帶比較重的那一個人
                j -= 1
            else: # 可以帶兩個人
                i += 1
                j -= 1
            ans += 1
        return ans

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