过桥的时间
难度:
标签:
题目描述
There are k workers who want to move n boxes from an old warehouse to a new one. You are given the two integers n and k, and a 2D integer array time of size k x 4 where time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi].
The warehouses are separated by a river and connected by a bridge. The old warehouse is on the right bank of the river, and the new warehouse is on the left bank of the river. Initially, all k workers are waiting on the left side of the bridge. To move the boxes, the ith worker (0-indexed) can :
- Cross the bridge from the left bank (new warehouse) to the right bank (old warehouse) in
leftToRightiminutes. - Pick a box from the old warehouse and return to the bridge in
pickOldiminutes. Different workers can pick up their boxes simultaneously. - Cross the bridge from the right bank (old warehouse) to the left bank (new warehouse) in
rightToLeftiminutes. - Put the box in the new warehouse and return to the bridge in
putNewiminutes. Different workers can put their boxes simultaneously.
A worker i is less efficient than a worker j if either condition is met:
leftToRighti + rightToLefti > leftToRightj + rightToLeftjleftToRighti + rightToLefti == leftToRightj + rightToLeftjandi > j
The following rules regulate the movement of the workers through the bridge :
- If a worker
xreaches the bridge while another workeryis crossing the bridge,xwaits at their side of the bridge. - If the bridge is free, the worker waiting on the right side of the bridge gets to cross the bridge. If more than one worker is waiting on the right side, the one with the lowest efficiency crosses first.
- If the bridge is free and no worker is waiting on the right side, and at least one box remains at the old warehouse, the worker on the left side of the river gets to cross the bridge. If more than one worker is waiting on the left side, the one with the lowest efficiency crosses first.
Return the instance of time at which the last worker reaches the left bank of the river after all n boxes have been put in the new warehouse.
Example 1:
Input: n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]] Output: 6 Explanation: From 0 to 1: worker 2 crosses the bridge from the left bank to the right bank. From 1 to 2: worker 2 picks up a box from the old warehouse. From 2 to 6: worker 2 crosses the bridge from the right bank to the left bank. From 6 to 7: worker 2 puts a box at the new warehouse. The whole process ends after 7 minutes. We return 6 because the problem asks for the instance of time at which the last worker reaches the left bank.
Example 2:
Input: n = 3, k = 2, time = [[1,9,1,8],[10,10,10,10]] Output: 50 Explanation: From 0 to 10: worker 1 crosses the bridge from the left bank to the right bank. From 10 to 20: worker 1 picks up a box from the old warehouse. From 10 to 11: worker 0 crosses the bridge from the left bank to the right bank. From 11 to 20: worker 0 picks up a box from the old warehouse. From 20 to 30: worker 1 crosses the bridge from the right bank to the left bank. From 30 to 40: worker 1 puts a box at the new warehouse. From 30 to 31: worker 0 crosses the bridge from the right bank to the left bank. From 31 to 39: worker 0 puts a box at the new warehouse. From 39 to 40: worker 0 crosses the bridge from the left bank to the right bank. From 40 to 49: worker 0 picks up a box from the old warehouse. From 49 to 50: worker 0 crosses the bridge from the right bank to the left bank. From 50 to 58: worker 0 puts a box at the new warehouse. The whole process ends after 58 minutes. We return 50 because the problem asks for the instance of time at which the last worker reaches the left bank.
Constraints:
1 <= n, k <= 104time.length == ktime[i].length == 41 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000
代码结果
运行时间: 184 ms, 内存: 21.3 MB
/*
思路：
1. 使用流式API对工人按照效率从高到低排序。
2. 模拟工人搬运箱子的过程，利用优先级队列来管理工人的状态。
3. 记录每个工人完成搬运箱子的时间，最终返回最后一个完成搬运的时间。
*/
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.stream.IntStream;
public class Solution {
public int lastWorkerTime(int n, int k, int[][] time) {
// 排序工人
int[] sortedIndices = IntStream.range(0, k)
.boxed()
.sorted((a, b) -> {
int efficiencyA = time[a][0] + time[a][2];
int efficiencyB = time[b][0] + time[b][2];
return efficiencyA == efficiencyB ? Integer.compare(a, b) : Integer.compare(efficiencyB, efficiencyA);
})
.mapToInt(i -> i)
.toArray();
// 优先级队列管理工人
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
int currentTime = 0;
int[] endTimes = new int[k];
for (int i = 0; i < n; i++) {
// 处理在当前时间完成的工人
while (!pq.isEmpty() && pq.peek()[0] <= currentTime) {
pq.poll();
}
// 分配最有效率的工人
int workerIndex = sortedIndices[i % k];
pq.offer(new int[] { currentTime + time[workerIndex][0] + time[workerIndex][1] + time[workerIndex][2] + time[workerIndex][3], workerIndex });
endTimes[workerIndex] = currentTime + time[workerIndex][0] + time[workerIndex][1] + time[workerIndex][2] + time[workerIndex][3];
currentTime++;
}
// 返回最后一个完成时间
return Arrays.stream(endTimes).max().orElse(0);
}
}
解释
方法:
该题解采用优先队列（堆）和模拟的方法来解决问题。首先，将工人根据其过桥时间（来回之和）排序，以优化选择过桥的工人顺序。使用两个优先队列（堆），分别管理在左岸和右岸等待过桥的工人，以及两个列表管理在左岸和右岸工作的工人。通过模拟整个过程，每次选择出下一个行动的工人，并根据当前的情景更新时间和工人的状态。当所有箱子都被搬运完毕后，返回最后一个到达左岸的时间。
时间复杂度:
O(nk log k)
空间复杂度:
O(k)
代码细节讲解
🦆
题解中提到了使用优先队列（堆）来管理工人状态，为什么选择使用优先队列而不是其他数据结构如队列或栈？
▷🦆
在模拟过程中，如何决定何时一个工人应从一个状态转移到另一个状态？请详细解释状态转移的条件。
▷🦆
题解中没有完全阐述如何处理工人在两岸的等待队列。请问当工人完成任务后，是如何决定他们下一步去向的？
▷