千问 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]));

// 等待过桥的工人：大顶堆，效率最低的优先
PriorityQueue<int[]> waitLeft = new PriorityQueue<>((a, b) -> b[0] - a[0]); // [效率值, 下标]
PriorityQueue<int[]> waitRight = new PriorityQueue<>((a, b) -> b[0] - a[0]);

// 正在工作的工人：小顶堆，按完成时间排序
PriorityQueue<int[]> workLeft = new PriorityQueue<>((a, b) -> a[1] - b[1]); // [下标, 完成时间]
PriorityQueue<int[]> 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]; // rightToLeft
workLeft.offer(new int[]{id, curTime + time[id][3]}); // 到达左岸后放箱子
}
// 3. 否则，如果还有箱子要搬且左侧有人，派左侧工人过桥
else if (remain > 0 && !waitLeft.isEmpty()) {
int id = waitLeft.poll()[0];
curTime += time[id][0]; // leftToRight
workRight.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((n+k) log k)，空间复杂度 O(k)，可以高效通过题目的大数据范围（n, k ≤ 10⁴）。