Time to Cross a Bridge - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
2532. Time to Cross a Bridge
Hard
50 Points
Array
Heap (Priority Queue)
Simulation
There are k workers who want to move n boxes from the right (old) warehouse to the left (new) warehouse. You are given the two integers n and k, and a 2D integer array time of size k x 4 where time[i] = [righti, picki, lefti, puti].
The warehouses are separated by a river and connected by a bridge. Initially, all k workers are waiting on the left side of the bridge. To move the boxes, the ith worker can do the following:
The ith worker is less efficient than the jth worker if either condition is met:
The following rules regulate the movement of the workers through the bridge:
Return the elapsed minutes at which the last box reaches the left side of the bridge.
Examples
Example 1
From 0 to 1 minutes: worker 2 crosses the bridge to the right.
From 1 to 2 minutes: worker 2 picks up a box from the right warehouse.
From 2 to 6 minutes: worker 2 crosses the bridge to the left.
From 6 to 7 minutes: worker 2 puts a box at the left 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 side of the bridge.
Example 2
Constraints
1 <= n, k <= 104
time.length == k
time[i].length == 4
1 <= lefti, picki, righti, puti <= 1000
2532. Time to Cross a Bridge
Hard
50 Points
Array
Heap (Priority Queue)
Simulation
There are k workers who want to move n boxes from the right (old) warehouse to the left (new) warehouse. You are given the two integers n and k, and a 2D integer array time of size k x 4 where time[i] = [righti, picki, lefti, puti].
The warehouses are separated by a river and connected by a bridge. Initially, all k workers are waiting on the left side of the bridge. To move the boxes, the ith worker can do the following:
The ith worker is less efficient than the jth worker if either condition is met:
The following rules regulate the movement of the workers through the bridge:
Return the elapsed minutes at which the last box reaches the left side of the bridge.
Examples
Example 1
From 0 to 1 minutes: worker 2 crosses the bridge to the right.
From 1 to 2 minutes: worker 2 picks up a box from the right warehouse.
From 2 to 6 minutes: worker 2 crosses the bridge to the left.
From 6 to 7 minutes: worker 2 puts a box at the left 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 side of the bridge.