【leetcode】881. Boats to Save Peo

1、题目描述

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.)

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)

Note:

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000

2、问题描述：

• 有一群人，有胖有瘦。有这样的一种船，最多坐两个人，并且一个船有个载重量limits，不能超过两个。求最少多少船可以一次把这些人全拉过去。

3、问题关键：

• 对于胖子，可能只能坐一个人，不太胖的可能再加入一个瘦子。
• 可以按照体重排序，对于每个胖子放入一个船，判断能不能再塞进去一个瘦子。胖子指针right，瘦子指针left。right每次--，res ++，如果可以塞进去一个瘦子那么left++。

4、C++代码：

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        if (people.empty()) return 0;
        sort(people.begin(), people.end());
        int left = 0, right = people.size() - 1;
        int res = 0;
        while(left <= right) {
            if (people[left] + people[right] <= limit)
                left ++;
            right --;
            res ++;
        }
        return res;
    }
};