千问 LeetCode 2532.过桥的时间 public int findCrossingTime(int n, int k, int[][] time)

这道题是LeetCode 2532“过桥的时间”一道经典的多优先队列模拟题。核心思路是用四个堆来管理工人的四种状态按规则模拟时间推进。下面给出一个清晰、可直接运行的Java解法class Solution {public int findCrossingTime(int n, int k, int[][] time) {// 1. 按效率排序leftToRight rightToLeft 越大效率越低相同时下标越大效率越低// 这里用稳定排序保证下标大的排在后面效率低Arrays.sort(time, (a, b) - (a[0] a[2]) - (b[0] b[2]));// 等待过桥的工人大顶堆效率最低的优先PriorityQueueint[] waitLeft new PriorityQueue((a, b) - b[0] - a[0]); // [效率值, 下标]PriorityQueueint[] waitRight new PriorityQueue((a, b) - b[0] - a[0]);// 正在工作的工人小顶堆按完成时间排序PriorityQueueint[] workLeft new PriorityQueue((a, b) - a[1] - b[1]); // [下标, 完成时间]PriorityQueueint[] workRight new PriorityQueue((a, b) - a[1] - b[1]);// 初始所有工人在左侧等待for (int i k - 1; i 0; i--) {waitLeft.offer(new int[]{i, 0}); // 效率值用下标代替因为已排序}int curTime 0;int remain n; // 剩余需要搬运的箱子数while (remain 0 || !workRight.isEmpty() || !waitRight.isEmpty()) {// 1. 将当前时间前完成工作的工人移到等待队列while (!workLeft.isEmpty() workLeft.peek()[1] curTime) {int id workLeft.poll()[0];waitLeft.offer(new int[]{id, 0});}while (!workRight.isEmpty() workRight.peek()[1] curTime) {int id workRight.poll()[0];waitRight.offer(new int[]{id, 0});}// 2. 优先让右侧工人过桥if (!waitRight.isEmpty()) {int id waitRight.poll()[0];curTime time[id][2]; // rightToLeftworkLeft.offer(new int[]{id, curTime time[id][3]}); // 到达左岸后放箱子}// 3. 否则如果还有箱子要搬且左侧有人派左侧工人过桥else if (remain 0 !waitLeft.isEmpty()) {int id waitLeft.poll()[0];curTime time[id][0]; // leftToRightworkRight.offer(new int[]{id, curTime time[id][1]}); // 到达右岸后搬箱子remain--;}// 4. 无人过桥时间跳到下一个事件发生的时间else {int nextTime Integer.MAX_VALUE;if (!workLeft.isEmpty()) nextTime Math.min(nextTime, workLeft.peek()[1]);if (!workRight.isEmpty()) nextTime Math.min(nextTime, workRight.peek()[1]);curTime nextTime;}}// 最后所有箱子已搬完但右侧可能还有工人未回到左岸// 需要让所有右侧工人包括正在工作的依次过桥while (!workRight.isEmpty()) {int[] worker workRight.poll();curTime Math.max(curTime, worker[1]) time[worker[0]][2];}while (!waitRight.isEmpty()) {int id waitRight.poll()[0];curTime time[id][2];}return curTime;}}关键点说明1. 效率排序先按 leftToRight rightToLeft 排序总和越大效率越低相同时下标大的效率低。排序后下标即可代表效率优先级。2. 四个堆的作用- waitLeft / waitRight等待过桥的工人大顶堆效率最低的先过桥。- workLeft / workRight正在工作的工人小顶堆按完成时间排序时间到了就移到等待队列。3. 模拟逻辑每个循环先处理完成工作的工人然后优先让右侧工人过桥其次才是左侧工人且需有剩余箱子。如果无人过桥时间跳到下一个完成事件。4. 收尾处理所有箱子搬完后右侧可能还有工人没回来需要让他们依次过桥回到左岸。这个解法的时间复杂度为 O((nk) log k)空间复杂度 O(k)可以高效通过题目的大数据范围n, k ≤ 10⁴。