排序 – shelterofly

目标

给你个整数数组 arr，其中每个元素都不相同。

请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。

每对元素对 [a,b] 如下：

a , b 均为数组 arr 中的元素
a < b
b - a 等于 arr 中任意两个元素的最小绝对差

示例 1：

输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]

示例 2：

输入：arr = [1,3,6,10,15]
输出：[[1,3]]

示例 3：

输入：arr = [3,8,-10,23,19,-4,-14,27]
输出：[[-14,-10],[19,23],[23,27]]

说明：

2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6

思路

找到数组 arr 中元素值距离最小的元素对，按照升序返回。升序指元素对内部升序，结果集中元素对第一个元素升序。

将数组排序，最小距离在相邻元素中产生。

代码


/**
 * @date 2026-01-26 8:44
 */
public class MinimumAbsDifference1200 {

    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> res = new ArrayList<>();
        int n = arr.length;
        int diff = Integer.MAX_VALUE;
        for (int i = 0; i < n - 1; i++) {
            diff = Math.min(diff, arr[i + 1] - arr[i]);
        }
        for (int i = 0; i < n - 1; i++) {
            if (arr[i + 1] - arr[i] == diff) {
                List<Integer> tmp = new ArrayList<>();
                tmp.add(arr[i]);
                tmp.add(arr[i + 1]);
                res.add(tmp);
            }
        }
        return res;
    }
}

性能

目标

给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。

从数组中选出任意 k 名学生的分数，使这 k 个分数间最高分和最低分的差值达到最小化。

返回可能的最小差值。

示例 1：

输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 1 种方法：
- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0

示例 2：

输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2

说明：

1 <= k <= nums.length <= 1000
0 <= nums[i] <= 10^5

思路

从 nums 中选择 k 个元素，求这 k 个元素中最大值与最小值的差的最小值。

要使差值最小，应该尽量缩小所选元素之间的距离。排序，使用定长滑动窗口，窗口内最大值与最小值的差即为 nums[r] - nums[l]。

代码


/**
 * @date 2026-01-26 9:59
 */
public class MinimumDifference1984 {

    public int minimumDifference(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        Arrays.sort(nums);
        int l = 0;
        int n = nums.length;
        for (int r = k - 1; r < n; r++) {
            res = Math.min(res, nums[r] - nums[l++]);
        }
        return res;
    }
}

性能

目标

一个数对 (a,b) 的数对和等于 a + b 。最大数对和是一个数对数组中最大的数对和。

比方说，如果我们有数对 (1,5) ，(2,3) 和 (4,4)，最大数对和为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。

给你一个长度为偶数 n 的数组 nums ，请你将 nums 中的元素分成 n / 2 个数对，使得：

nums 中每个元素恰好在一个数对中，且
最大数对和的值最小。

请你在最优数对划分的方案下，返回最小的最大数对和。

示例 1：

输入：nums = [3,5,2,3]
输出：7
解释：数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。

示例 2：

输入：nums = [3,5,4,2,4,6]
输出：8
解释：数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2) 。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。

说明：

n == nums.length
2 <= n <= 10^5
n 是偶数。
1 <= nums[i] <= 10^5

思路

将长度为偶数的数组 nums 划分成若干数对，求这些数对和的最大值的最小值。

每种划分方案可以得到数对的最大值，取不同方案中最大值的最小值。

容易猜到划分方案应该是最小值与最大值组成数对，次小值与次大值组成数对，以此类推。

可以使用交换论证法来证明，如果存在一个更优的方案，那么可以通过局部交换操作，将其逐步调整为贪心方案，且每一步都不增加代价（或保持最优）。

代码


/**
 * @date 2026-01-26 11:32
 */
public class MinPairSum1877 {

    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n / 2; i++) {
            res = Math.max(res, nums[i] + nums[n - 1 - i]);
        }
        return res;
    }

}

性能

目标

给你一个网格图，由 n + 2 条横线段和 m + 2 条竖线段组成，一开始所有区域均为 1 x 1 的单元格。

所有线段的编号从 1 开始。

给你两个整数 n 和 m 。

同时给你两个整数数组 hBars 和 vBars 。

hBars 包含区间 [2, n + 1] 内互不相同的横线段编号。
vBars 包含 [2, m + 1] 内互不相同的竖线段编号。

如果满足以下条件之一，你可以移除两个数组中的部分线段：

如果移除的是横线段，它必须是 hBars 中的值。
如果移除的是竖线段，它必须是 vBars 中的值。

请你返回移除一些线段后（可能不移除任何线段），剩余网格图中最大正方形空洞的面积，正方形空洞的意思是正方形内部不含有任何线段。

示例 1：

输入：n = 2, m = 1, hBars = [2,3], vBars = [2]
输出：4
解释：左边的图是一开始的网格图。
横线编号的范围是区间 [1,4] ，竖线编号的范围是区间 [1,3] 。
可以移除的横线段为 [2,3] ，竖线段为 [2] 。
一种得到最大正方形面积的方法是移除横线段 2 和竖线段 2 。
操作后得到的网格图如右图所示。
正方形空洞面积为 4。
无法得到面积大于 4 的正方形空洞。
所以答案为 4 。

示例 2：

输入：n = 1, m = 1, hBars = [2], vBars = [2]
输出：4
解释：左边的图是一开始的网格图。
横线编号的范围是区间 [1,3] ，竖线编号的范围是区间 [1,3] 。
可以移除的横线段为 [2] ，竖线段为 [2] 。
一种得到最大正方形面积的方法是移除横线段 2 和竖线段 2 。
操作后得到的网格图如右图所示。
正方形空洞面积为 4。
无法得到面积大于 4 的正方形空洞。
所以答案为 4 。

示例 3：

输入：n = 2, m = 3, hBars = [2,3], vBars = [2,3,4]
输出：9
解释：左边的图是一开始的网格图。
横线编号的范围是区间 [1,4] ，竖线编号的范围是区间 [1,5] 。
可以移除的横线段为 [2,3] ，竖线段为 [2,3,4] 。
一种得到最大正方形面积的方法是移除横线段 2、3 和竖线段 3、4 。
操作后得到的网格图如右图所示。
正方形空洞面积为 9。
无法得到面积大于 9 的正方形空洞。
所以答案为 9 。

说明：

1 <= n <= 10^9
1 <= m <= 10^9
1 <= hBars.length <= 100
2 <= hBars[i] <= n + 1
1 <= vBars.length <= 100
2 <= vBars[i] <= m + 1
hBars 中的值互不相同。
vBars 中的值互不相同。

思路

有一个网格图由 n + 2 条横线段编号为 1 ~ n + 2 和 m + 2 条竖线段编号为 1 ~ m + 2 组成，单元格为 1 x 1，即横线间隔为 1，竖线间隔为 1。有两个数组 hBars 与 vBars，给出了横线段的编号 2 ~ n + 1 与竖线段编号 2 ~ m + 1 内的线段。删除其中的一些线段，使得空洞的正方形面积最大，返回面积的最大值。

要使空洞最大，能删尽删，找出两个数组线段编号连续的长度最大值，取二者的最小值（正方形），加一（删掉 k 条线段，空洞的边长为 k + 1）后平方即可。

代码


/**
 * @date 2026-01-15 9:08
 */
public class MaximizeSquareHoleArea2943 {

    public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        Arrays.sort(hBars);
        Arrays.sort(vBars);
        int hmax = getMaxInterval(hBars);
        int vmax = getMaxInterval(vBars);
        int min = Math.min(hmax, vmax) + 1;
        return min * min;
    }

    private int getMaxInterval_v1(int[] bars) {
        int l = bars.length;
        int max = 1;
        int i = 0;
        while (i < l - 1) {
            int start = i;
            do {
                i++;
            } while (i < l && bars[i - 1] + 1 == bars[i]);
            max = Math.max(max, i - start);
        }
        return max;
    }

}

性能

2402.会议室III

目标

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在半闭时间区间 [starti, endi) 举办。所有 starti 的值互不相同。

会议将会按以下方式分配给会议室：

每场会议都会在未占用且编号最小的会议室举办。
如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间相同。
当会议室处于未占用状态时，将会优先提供给原开始时间更早的会议。

返回举办最多次会议的房间编号。如果存在多个房间满足此条件，则返回编号最小的房间。

半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但不包括 b 。

示例 1：

输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
输出：0
解释：
- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。
会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。

示例 2：

输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
输出：1
解释：
- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。 
- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。 
- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。 
会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。

说明：

1 <= n <= 100
1 <= meetings.length <= 10^5
meetings[i].length == 2
0 <= starti < endi <= 5 * 10^5
starti 的所有值互不相同

思路

有 n 个会议室，编号为 0 ~ n - 1。有一个二维数组，meetings[i] 表示 [starti, endi) 范围内需要举办一场会议，会优先使用未被占用且编号最小的会议室。如果没有会议室可用，则需要延后举办，如果同一时间有多个会议需要举办，原开始时间最小的优先举办。

这个题目的关键点是，当有多个满足条件的会议室时，选择编号最小的，而不是最早可用的。需要使用两个优先队列，一个追踪会议室的最早空闲时间，另一个则追踪空闲会议室中编号最小的。将会议按照开始时间排序，按顺序遍历，将可选的会议室加入空闲编号堆，如果这个堆非空，从中取一个会议室，并将结束时间（可用时间）放入空闲时间堆中；否则，从空闲时间堆中取一个会议室，将其空闲时间加上会议持续时间后再放入堆中。

代码


/**
 * @date 2025-12-30 14:01
 */
public class MostBooked2402 {

    public int mostBooked(int n, int[][] meetings) {
        int[] cnt = new int[n];
        PriorityQueue<int[]> rooms = new PriorityQueue<>((a, b) -> {
            int compare = a[0] - b[0];
            if (compare != 0) {
                return compare;
            }
            return a[1] - b[1];
        });
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (int i = 0; i < n; i++) {
            rooms.offer(new int[]{0, i});
        }
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        for (int[] meeting : meetings) {
            while (!rooms.isEmpty() && rooms.peek()[0] <= meeting[0]) {
                q.offer(rooms.poll());
            }
            int[] room;
            if (!q.isEmpty()) {
                room = q.poll();
                rooms.offer(new int[]{meeting[1], room[1]});
            } else {
                room = rooms.poll();
                rooms.offer(new int[]{room[0] + meeting[1] - meeting[0], room[1]});
            }
            cnt[room[1]]++;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (cnt[i] > cnt[res]) {
                res = i;
            }
        }
        return res;
    }

}

性能

3075.幸福值最大化的选择方案

目标

给你一个长度为 n 的数组 happiness ，以及一个正整数 k 。

n 个孩子站成一队，其中第 i 个孩子的幸福值是 happiness[i] 。你计划组织 k 轮筛选从这 n 个孩子中选出 k 个孩子。

在每一轮选择一个孩子时，所有尚未被选中的孩子的幸福值将减少 1 。注意，幸福值不能变成负数，且只有在它是正数的情况下才会减少。

选择 k 个孩子，并使你选中的孩子幸福值之和最大，返回你能够得到的最大值。

示例 1：

输入：happiness = [1,2,3], k = 2
输出：4
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
- 选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
所选孩子的幸福值之和为 3 + 1 = 4 。

示例 2：

输入：happiness = [1,1,1,1], k = 2
输出：1
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 1 的任意一个孩子。剩余孩子的幸福值变为 [0,0,0] 。
- 选择幸福值为 0 的孩子。剩余孩子的幸福值变为 [0,0] 。
所选孩子的幸福值之和为 1 + 0 = 1 。

示例 3：

输入：happiness = [2,3,4,5], k = 1
输出：5
解释：按以下方式选择 1 个孩子：
- 选择幸福值为 5 的孩子。剩余孩子的幸福值变为 [1,2,3] 。
所选孩子的幸福值之和为 5 。

说明：

1 <= n == happiness.length <= 2 * 10^5
1 <= happiness[i] <= 10^8
1 <= k <= n

思路

n 个孩子站成一排，happiness[i] 表示第 i 个孩子的幸福值，从中选 k 个孩子，每选择一个孩子，剩余孩子的幸福值会减少 1（但不会是负值），求所选孩子幸福值之和的最大值。

贪心策略，优先选幸福值最大的，因为下限为 0，如果放后面选减的更多。

代码


/**
 * @date 2025-12-25 8:51
 */
public class MaximumHappinessSum3075 {

    public long maximumHappinessSum(int[] happiness, int k) {
        long res = 0;
        int sub = 0;
        Arrays.sort(happiness);
        int n = happiness.length;
        for (int i = n - 1; sub < k; i--) {
            res += Math.max(0, happiness[i] - sub++);
        }
        return res;
    }
}

性能

3074.重新分装苹果

目标

给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。

一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。

请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的最小数量。

注意，同一个包裹中的苹果可以分装到不同的箱子中。

示例 1：

输入：apple = [1,3,2], capacity = [4,3,1,5,2]
输出：2
解释：使用容量为 4 和 5 的箱子。
总容量大于或等于苹果的总数，所以可以完成重新分装。

示例 2：

输入：apple = [5,5,5], capacity = [2,4,2,7]
输出：4
解释：需要使用所有箱子。

说明：

1 <= n == apple.length <= 50
1 <= m == capacity.length <= 50
1 <= apple[i], capacity[i] <= 50
输入数据保证可以将包裹中的苹果重新分装到箱子中。

思路

apple[i] 表示第 i 个包裹中苹果的数量，capacity[i] 表示第 i 个箱子的容量，现在需要将包裹中的苹果分装到箱子中，求所需箱子的最小数量。

累加所有苹果的数量，优先选择容量大的箱子装箱，记录箱子个数。

代码


/**
 * @date 2025-12-24 8:44
 */
public class MinimumBoxes3074 {

    public int minimumBoxes(int[] apple, int[] capacity) {
        int sum = 0;
        for (int num : apple) {
            sum += num;
        }
        Arrays.sort(capacity);
        int res = 0;
        for (int i = capacity.length - 1; i >= 0; i--) {
            if (sum <= 0) {
                break;
            }
            sum -= capacity[i];
            res++;
        }
        return res;
    }
}

性能

2054.两个最好的不重叠活动

目标

给你一个下标从 0 开始的二维整数数组 events ，其中 events[i] = [startTimei, endTimei, valuei] 。第 i 个活动开始于 startTimei ，结束于 endTimei ，如果你参加这个活动，那么你可以得到价值 valuei 。你最多可以参加两个时间不重叠活动，使得它们的价值之和最大。

请你返回价值之和的最大值。

注意，活动的开始时间和结束时间是包括在活动时间内的，也就是说，你不能参加两个活动且它们之一的开始时间等于另一个活动的结束时间。更具体的，如果你参加一个活动，且结束时间为 t ，那么下一个活动必须在 t + 1 或之后的时间开始。

示例 1:

输入：events = [[1,3,2],[4,5,2],[2,4,3]]
输出：4
解释：选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。

示例 2：

输入：events = [[1,3,2],[4,5,2],[1,5,5]]
输出：5
解释：选择活动 2 ，价值和为 5 。

示例 3：

输入：events = [[1,5,3],[1,5,1],[6,6,5]]
输出：8
解释：选择活动 0 和 2 ，价值之和为 3 + 5 = 8 。

说明：

2 <= events.length <= 10^5
events[i].length == 3
1 <= startTimei <= endTimei <= 10^9
1 <= valuei <= 10^6

思路

有一个二维数组 events，events[i] 表示事件 i 的 (开始时间，结束时间，价值) 三元组，至多参加两个活动，这两个活动不能重叠 (结束时间与开始时间也不能重叠)，求参加活动的最大价值。

根据开始时间排序，二分查找第一个大于结束时间的下标，维护后缀最大值。

代码


/**
 * @date 2025-12-23 8:53
 */
public class MaxTwoEvents2054 {

    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        int res = 0;
        int n = events.length;
        int[] suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = Math.max(suffix[i + 1], events[i][2]);
        }
        for (int[] event : events) {
            int index = bs(events, event[1]);
            res = Math.max(res, event[2] + suffix[index]);
        }
        return res;
    }

    public int bs(int[][] events, int target) {
        int l = 0;
        int r = events.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (events[m][0] <= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

}

性能

3531.统计被覆盖的建筑

目标

给你一个正整数 n，表示一个 n x n 的城市，同时给定一个二维数组 buildings，其中 buildings[i] = [x, y] 表示位于坐标 [x, y] 的一个唯一建筑。

如果一个建筑在四个方向（左、右、上、下）中每个方向上都至少存在一个建筑，则称该建筑被覆盖。

返回被覆盖的建筑数量。

示例 1：

输入: n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]
输出: 1
解释:
只有建筑 [2,2] 被覆盖，因为它在每个方向上都至少存在一个建筑：
上方 ([1,2])
下方 ([3,2])
左方 ([2,1])
右方 ([2,3])
因此，被覆盖的建筑数量是 1。

示例 2：

输入: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]
输出: 0
解释:
没有任何一个建筑在每个方向上都有至少一个建筑。

示例 3：

输入: n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]
输出: 1
解释:
只有建筑 [3,3] 被覆盖，因为它在每个方向上至少存在一个建筑：
上方 ([1,3])
下方 ([5,3])
左方 ([3,2])
右方 ([3,5])
因此，被覆盖的建筑数量是 1。

说明：

2 <= n <= 10^5
1 <= buildings.length <= 10^5
buildings[i] = [x, y]
1 <= x, y <= n
buildings 中所有坐标均唯一。

思路

二维数组 buildings 表示建筑的坐标，如果建筑的上下左右均存在其它建筑，则称该建筑被包围。统计被包围建筑的个数。

只需记录每一行每一列的最大值与最小值，判断当前建筑是否在其中。

代码


/**
 * @date 2025-12-11 14:03
 */
public class CountCoveredBuildings3531 {

    public int countCoveredBuildings_v1(int n, int[][] buildings) {
        int[] minX = new int[n + 1];
        int[] maxX = new int[n + 1];
        int[] minY = new int[n + 1];
        int[] maxY = new int[n + 1];
        Arrays.fill(minX, n + 1);
        Arrays.fill(minY, n + 1);
        for (int[] building : buildings) {
            int x = building[0];
            int y = building[1];
            minX[y] = Math.min(minX[y], x);
            maxX[y] = Math.max(maxX[y], x);
            minY[x] = Math.min(minY[x], y);
            maxY[x] = Math.max(maxY[x], y);
        }
        int res = 0;
        for (int[] building : buildings) {
            int x = building[0];
            int y = building[1];
            if (x > minX[y] && x < maxX[y] && y > minY[x] && y < maxY[x]) {
                res++;
            }
        }
        return res;
    }

}

性能

2141.同时运行N台电脑的最长时间

目标

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑运行 batteries[i] 分钟。你想使用这些电池让全部 n 台电脑同时运行。

一开始，你可以给每台电脑连接至多一个电池。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作任意次。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。

注意，你不能给电池充电。

请你返回你可以让 n 台电脑同时运行的最长分钟数。

示例 1：

输入：n = 2, batteries = [3,3,3]
输出：4
解释：
一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 1 连接。
2 分钟后，将第二台电脑与电池 1 断开连接，并连接电池 2 。注意，电池 0 还可以供电 1 分钟。
在第 3 分钟结尾，你需要将第一台电脑与电池 0 断开连接，然后连接电池 1 。
在第 4 分钟结尾，电池 1 也被耗尽，第一台电脑无法继续运行。
我们最多能同时让两台电脑同时运行 4 分钟，所以我们返回 4 。

示例 2：

输入：n = 2, batteries = [1,1,1,1]
输出：2
解释：
一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 2 连接。
一分钟后，电池 0 和电池 2 同时耗尽，所以你需要将它们断开连接，并将电池 1 和第一台电脑连接，电池 3 和第二台电脑连接。
1 分钟后，电池 1 和电池 3 也耗尽了，所以两台电脑都无法继续运行。
我们最多能让两台电脑同时运行 2 分钟，所以我们返回 2 。

说明：

1 <= n <= batteries.length <= 10^5
1 <= batteries[i] <= 10^9

思路

有 m 个电池，batteries[i] 表示第 i 个电池的电量，将电池分成 n 组，要求每组电池电量和的最小值最大。

贪心的做法是找到上界 x = sum / n，从大到小遍历电池容量：

如果大于 x，超过的部分也不能再使用了，因为一个电池在同一时间只能为一台电池供电，问题规模缩小，sum -= batteries[i]，n--。
如果小于等于 x，可以用完了再接上下一个电池，不会出现一个电池供两台电脑的情况，因为如果出现这种情况，总是可以将其放到一台的末尾与一台的开头将它们错开。

代码


/**
 * @date 2025-12-01 8:57
 */
public class MaxRunTime2141 {

    public long maxRunTime(int n, int[] batteries) {
        long sum = 0L;
        for (int battery : batteries) {
            sum += battery;
        }
        Arrays.sort(batteries);
        int m = batteries.length;
        for (int i = m - 1; i >= 0; i--) {
            long x = sum / n;
            if (batteries[i] <= x) {
                return x;
            }
            sum -= batteries[i];
            n--;
        }
        return -1;
    }
}

2026 年 1 月
一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31