LeetCode 881. 救生艇

原题链接

题目描述

第 $i$ 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

数据范围

$1 \le people.length \le 50000$

$1 \le people[i] \le limit \le 30000$

样例

输入样例1：

people = [1,2], limit = 3

输出样例1：

1

样例1解释：

$1$ 艘船载 $(1, 2)$

输入样例2：

people = [3,2,2,1], limit = 3

输出样例2：

3

样例2解释：

$3$ 艘船分别载 $(1, 2), (2)$ 和 $(3)$

输入样例3：

people = [3,5,3,4], limit = 5

输出样例3：

4

样例3解释：

$4$ 艘船分别载 $(3), (3), (4), (5)$

思路

每艘船最多只能坐两个人，要使得船的数量最少，考虑当前最重的带一个当前最轻的。如果当前最重的不能带当前最轻的，只能让最重的单独坐一艘船。

代码

C++

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

Java

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int res = 0, n = people.length;
        for ( int l = 0, r = n - 1; l <= r; r --, res ++ )
            if ( people[l] + people[r] <= limit ) l ++;
        return res;
    }
}