双指针

【leetcode】881. Boats to Save Peo

2019-05-15  本文已影响0人  邓泽军_3679

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、问题描述:

3、问题关键:

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;
    }
};
上一篇下一篇

猜你喜欢

热点阅读