日期: 2024 年 6 月 10 日

目标

给定数组 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 * 10^4
• 1 <= people[i] <= limit <= 3 * 10^4

思路

给定一个数组，数组元素是待救援人员的体重，每条救生艇最多载两人且体重不超过限制，问最少需要多少救生艇。

尽可能多地让两人乘一艇，将体重轻的与重的搭配，如果都是轻的则造成运力浪费。

因此先按体重从小到大排序，然后使用双指针将重的与轻的搭配即可。

代码

/**
 * @date 2024-06-10 21:18
 */
public class NumRescueBoats881 {

    public int numRescueBoats(int[] people, int limit) {
        int n = people.length;
        Arrays.sort(people);
        int end = Arrays.binarySearch(people, limit);
        if (end < 0) {
            end = -end - 1;
        }
        // [end,n) 下标小于end的元素均比limit小，end 为0则可直接返回n
        int res = n - end;
        int start = 0;
        while (start < end) {
            // 如果start == end -1 即仅剩start一个元素 不再重复累加
            // start < end 防止end - 1为负即end==0
            // 由于取开区间，不包括end，因此从end-1开始
            while (start < end - 1 && people[start] + people[end - 1] > limit) {
                end--;
                res++;
            }
            start++;
            end--;
            res++;
        }
        return res;
    }
}

性能