LintCode 1601: Boats to Save People 双指针经典题

1601 · Boats to Save People
Algorithms
Medium

Description
The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)

1 \leq people.length \leq 500001≤people.length≤50000
1 \leq people[i] \leq limit \leq 300001≤people[i]≤limit≤30000
Example
Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)
Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)
Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

解法1：类似two sum的相向双指针，胖瘦组合。

class Solution {
public:
    /**
     * @param people: The i-th person has weight people[i].
     * @param limit: Each boat can carry a maximum weight of limit.
     * @return: Return the minimum number of boats to carry every given person. 
     */
    int numRescueBoats(vector<int> &people, int limit) {
        int len = people.size();
        sort(people.begin(), people.end());
        int start = 0, end = len - 1;
        int count = 0;
        while (start < end) {
            if (people[start] + people[end] <= limit) {
                start++;
                end--;
            } else {
                end--;
            }
            count++;
        }
        //分刚好分完和还剩一个两种情况
        if (start != end) return count; 
        return count + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

注意这题如果没有每条船最多坐2人这个条件就不能用贪婪法了，我一开始的做法是先将数组排序，然后从小往大把尽量多的人放到一条船上。代码如下：

class Solution {
public:
    /**
     * @param people: The i-th person has weight people[i].
     * @param limit: Each boat can carry a maximum weight of limit.
     * @return: Return the minimum number of boats to carry every given person. 
     */
    int numRescueBoats(vector<int> &people, int limit) {
        int len = people.size();
        sort(people.begin(), people.end());
        int start = 0, end = len - 1;
        int count = 0;
        while (start < end) {
            if (people[start] + people[end] <= limit) {
                start++;
                end--;
            } else {
                end--;
            }
            count++;
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

但这是不对的，因为对于下面的例子，
1,1,1,1,3,3,4,5 limit=5
那么结果是5，因为[1,1,1,1],[3],[3],[4],[5]。
但正确结果是4，因为 [1,4],[3,1,1],[3,1],[5]。
也就是有些空间被浪费了。