题目描述

people数组记录了每个人的体重，people[i]表示第i个人的体重，每条船有最大载重限制。每条船最多一次性载两个人，要求这两人的体重之和小于最大载重限制。

给定每个人的体重和船的最大载重限制，返回最少需要多少条船才能载所有人。（保证单个人的体重不大于船的最大载重）

样例

输入：people = [3,2,2,1], limit = 3
输出：3
说明：需要三条船，分别为(3), (1, 2), (2)

输入：people = [3,5,3,4], limit = 5
输出: 4
说明：需要四条船，分别为(5), (4), (3), (3)

算法

(贪心) $O(n)$

首先认为每个人都需要一条船，这样一定是能载走所有人的，然后再去搜寻能够合并到一条船上的两个人，要求就是两个人的体重之和不超过limit。

首先对people数组从小到大进行排序，用两个指针（l和r指针）分别从左右两边开始搜寻，一开始l指向体重最小的人，如果people[l]+people[r]>limit，则说明people[r]还是太重了，r指针向左移，直到找到第一个people[l]+people[r]<=limit，这时候people[r]是能跟people[l]放在同一条船上的人里面体重最大的人，这时候就能减少一条船，然后l指针向右移，按照上述策略开始找能跟people[l+1]放在一条船上的体重最大的人，依次类推，直到l指针和r指针相遇，搜寻暂停。

该算法的证明参考 Proof of the correctness of the greedy algorithm

时间复杂度分析：$O(n)$

C++ 代码

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int res = people.size();
        sort(people.begin(),people.end());
        int l = 0;
        int r = people.size()-1;
        while(l<r){
            if(people[l]+people[r]>limit){//说明people[r]还是太重了 r左移
                r--;
            }
            else{//说明people[l]+people[r]<=limit 满足载重要求 可以合并到一条船上
                res--;
                l++;//l右移 开始对people[l+1]找同伴
                r--;
            }
        }
        return res;
    }
};