881. Boats to Save People

Description

image-20210827222615085

Solution

Greedy, because every boat is required to save most 2 people, so we could greedily let every boat loads 2 people. But a tricky point is, intuitively we should let each boat takes as heavier as possible, but actually, if we could putpeople[-1] with people[1] instead of people[-1] with people[0], we still could let people[-2] with people[1], so just let first and last together and we will get the correct answer.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numRescueBoats(vector<int> &people, int limit) {
        int ans = 0;
        sort(people.begin(), people.end());
        int light = 0, heavy = people.size() - 1;
        while (light <= heavy) {
            if (people[light] + people[heavy] > limit) {
                --heavy;
            } else {
                ++light;
                --heavy;
            }
            ++ans;
        }
        return ans;
    }
};