0881. Boats to Save People

题目信息

题号:

0881

难度:

Medium

主题:

人员分组、载重限制、最少船数

原题:

LeetCode 0881

重点:

每艘船最多载两个人且总重量不能超过 limit;每个人必须恰好登上一艘船,返回最少船数

题目重述

给定数组 people,其中每个元素表示一个人的体重,以及每艘救生艇的载重上限 limit。每艘船最多乘坐两个人,并且船上人员总重量不能超过 limit。

需要让所有人都登船,每个人恰好乘坐一艘船,船的数量不限。请返回完成救援所需的最少救生艇数量。题目保证每个人的体重都不超过载重上限,因此单独乘船总是可行。

1 <= people.length <= 5 * 10^4,1 <= people[i] <= limit <= 3 * 10^4。

自建示例

只能有一对能够同船:

输入:people = [1,2,2,3], limit = 3
输出:3
解释:可以让体重 1 和其中一名体重 2 的人同船,另一名体重 2 的人和体重 3 的人分别单独乘船,共三艘;任何船都不能载三人。

只有一名人员且体重达到上限:

输入:people = [4], limit = 4
输出:1
解释:人员数量达到允许的最小值,且唯一人员可以单独乘船。至少需要一艘船,因此答案为 1。