Poison

881. Boats to Save People

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int boats = 0;
        Arrays.sort(people);

        int light = 0, heavy = people.length - 1;
        while (light <= heavy) {
            if (people[light] + people[heavy] <= limit) {
                // 体重最轻的人和体重最重的人可以同乘一艘船
                light++;
                heavy--;
                boats++;
            } else {
                // 体重最轻的人和体重最重的人不可以同乘一艘船，此时这个胖子无法和其他人一起乘船了，因为剩下的人都比当前的瘦子重，这个胖子只能单独乘一艘船
                heavy--;
                boats++;
            }
        }

        return boats;
    }
}

先让瘦子上船能够便于解题。如果先让胖子上船，那么需要找第二胖的胖子，并不便于解题。

Reference

881. Boats to Save People