881. 救生艇

如果最轻的人可以和任何人配对，那么它也可以和最重的人配对。而如果不行，那最重的人无论如何都只能一个人做了。

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int begin = 0, end = people.size() - 1;
        int ret = 0;
        while(begin <= end) // 当相等时表示最后只有1个人了，无论什么情况都需要再加一艘船。
        {
            if(people[begin] + people[end] <= limit)
                ++begin;
            --end;
            ++ret;
        }
        return ret;
    }
};

最重的走的时候，如果能带，一定要带个人走，这才是合理的，否则，例如【1,3】，limit = 4，这种，3先自己坐船走，1只能再乘一条船。显然不合理。那最终的走的时候，带谁走呢，显然是最轻的（当然他也可能能够次轻的同乘一条船），反证下，如果因为它带了最轻的，导致次轻的无法跟其他人同船，那么次轻的也一定无法跟最重的乘船。如果次轻的可以跟其他人同船，则反正同船了，跟谁效果都一样。所以不会因为最重的选择了最轻的同船，导致后面的配对结果更坏。