【LeetCode】881 救生艇 中等题

救生艇 中等题"/>

【LeetCode】881 救生艇 中等题

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

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

返回 承载所有人所需的最小船数 。

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

提示：

• 1 <= people.length <= 5 * 104
• 1 <= people[i] <= limit <= 3 * 104

思路：

贪心算法，对给定数组进行排序后，从左边第一个开始，跟右边最后一个进行配对，由于每艘船最多载两人，如果当前最轻的人和最重的人加起来超过了limit，说明重的人可以自己做一辆船，轻的人再和下一个人进行配对，这样可以保证尽可能地让船载两个人

代码：

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