题目描述
leetcode 困难题
共有 k 位工人计划将 n 个箱子从旧仓库移动到新仓库。给你两个整数 n 和 k，以及一个二维整数数组 time ，数组的大小为 k x 4 ，其中 time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi] 。
一条河将两座仓库分隔，只能通过一座桥通行。旧仓库位于河的右岸，新仓库在河的左岸。开始时，所有 k 位工人都在桥的左侧等待。为了移动这些箱子，第 i 位工人（下标从 0 开始）可以：
- 从左岸（新仓库）跨过桥到右岸（旧仓库），用时 leftToRighti 分钟。
- 从旧仓库选择一个箱子，并返回到桥边，用时 pickOldi 分钟。不同工人可以同时搬起所选的箱子。
- 从右岸（旧仓库）跨过桥到左岸（新仓库），用时 rightToLefti 分钟。
- 将箱子放入新仓库，并返回到桥边，用时 putNewi 分钟。不同工人可以同时放下所选的箱子。
如果满足下面任一条件，则认为工人 i 的 效率低于 工人 j ：
- leftToRighti + rightToLefti > leftToRightj + rightToLeftj
- leftToRighti + rightToLefti == leftToRightj + rightToLeftj 且 i > j
工人通过桥时需要遵循以下规则：
- 如果工人 x 到达桥边时，工人 y 正在过桥，那么工人 x 需要在桥边等待。
- 如果没有正在过桥的工人，那么在桥右边等待的工人可以先过桥。如果同时有多个工人在右边等待，那么 效率最低 的工人会先过桥。
- 如果没有正在过桥的工人，且桥右边也没有在等待的工人，同时旧仓库还剩下至少一个箱子需要搬运，此时在桥左边的工人可以过桥。如果同时有多个工人在左边等待，那么 效率最低 的工人会先过桥。
所有 n 个盒子都需要放入新仓库，请你返回最后一个搬运箱子的工人 到达河左岸 的时间。
示例1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 输入：n = 3, k = 2, time = [[1,9,1,8],[10,10,10,10]]
输出：50
解释：
从 0 到 10 ：工人 1 从左岸过桥到达右岸。
从 10 到 20 ：工人 1 从旧仓库搬起一个箱子。
从 10 到 11 ：工人 0 从左岸过桥到达右岸。
从 11 到 20 ：工人 0 从旧仓库搬起一个箱子。
从 20 到 30 ：工人 1 从右岸过桥到达左岸。
从 30 到 40 ：工人 1 将箱子放入新仓库。
从 30 到 31 ：工人 0 从右岸过桥到达左岸。
从 31 到 39 ：工人 0 将箱子放入新仓库。
从 39 到 40 ：工人 0 从左岸过桥到达右岸。
从 40 到 49 ：工人 0 从旧仓库搬起一个箱子。
从 49 到 50 ：工人 0 从右岸过桥到达左岸。
从 50 到 58 ：工人 0 将箱子放入新仓库。
整个过程在 58 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 50 。
|
提示1：
1
2
3
4
| 1 <= n, k <= 10^4
time.length == k
time[i].length == 4
1 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000
|
模拟
通过四个堆进行模拟，分别是：
- $leftBridge$ 左边等桥的工人序号，堆顶为效率最小的工人。
- $rightBridge$ 右边等桥的工人序号，堆顶为效率最小的工人。
- $leftPuttingNew$ 左边正在搬箱子的工人，$int[0]$ 为该工人搬运当前箱子完成的时间，$int[1]$ 为工人序号，堆顶为搬运完成时间最早的工人。
- $rightPickingOld$ 右边正在搬箱子的工人，$int[0]$ 为该工人搬运当前箱子完成的时间，$int[1]$ 为工人序号，堆顶为搬运完成时间最早的工人。
初始化当前时间为 $0$，模拟工人搬运过程，由于关注的是最后一个搬运箱子的工人到达左岸的时间，所以中止条件为箱子搬完且右岸不存在任何工人。
按照题意，每次循环时，如果右边等桥的人非空，右边等桥的堆顶工人出堆过桥，更新当前时间为过桥后的时间，并将工人放入左边搬运箱子的堆中；否则如果左边等桥的人非空且存在箱子未搬运，就将左边等桥的堆顶工人出堆过桥，更新当前时间为过桥后的时间，并将工人放入右边搬运箱子的堆中，箱子数量减一；如果以上两个条件均不满足，则说明当前时间过小，工人未搬完箱子，更新时间为左右岸搬完箱子的最小时间即可。
显然在上面的三个判断之前，还需要判断左右岸正在搬箱子的工人，如果已经搬完箱子了，就将其放入等桥的队列中。
循环结束时，当前时间为答案。
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
32
33
34
35
36
37
38
39
| class Solution {
public int findCrossingTime(int n, int k, int[][] time) {
Comparator<Integer> cmp = (a, b) -> {
int d = (time[b][0] + time[b][2]) - (time[a][0] + time[a][2]);
return d != 0 ? d : b - a;
};
PriorityQueue<Integer> leftBridge = new PriorityQueue<>(cmp);
PriorityQueue<Integer> rightBridge = new PriorityQueue<>(cmp);
PriorityQueue<int[]> leftPuttingNew = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
PriorityQueue<int[]> rightPickingOld = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
leftBridge.addAll(IntStream.range(0, k).boxed().toList());
int curTime = 0;
while (n + rightPickingOld.size() + rightBridge.size() > 0) {
while (!rightPickingOld.isEmpty() && rightPickingOld.peek()[0] <= curTime) {
rightBridge.offer(rightPickingOld.poll()[1]);
}
while (!leftPuttingNew.isEmpty() && leftPuttingNew.peek()[0] <= curTime) {
leftBridge.offer(leftPuttingNew.poll()[1]);
}
if (!rightBridge.isEmpty()) {
int worker = Objects.requireNonNull(rightBridge.poll());
curTime += time[worker][2];
leftPuttingNew.offer(new int[]{curTime + time[worker][3], worker});
} else if (n > 0 && !leftBridge.isEmpty()) {
int worker = Objects.requireNonNull(leftBridge.poll());
curTime += time[worker][0];
rightPickingOld.offer(new int[]{curTime + time[worker][1], worker});
n--;
} else {
curTime = Math.min(
rightPickingOld.isEmpty() ? Integer.MAX_VALUE : rightPickingOld.peek()[0],
leftPuttingNew.isEmpty() ? Integer.MAX_VALUE : leftPuttingNew.peek()[0]);
}
}
return curTime;
}
}
|