Time to Cross a Bridge
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 i^th worker can do the following:
- Cross the bridge to the right side in
rightiminutes. - Pick a box from the right warehouse in
pickiminutes. - Cross the bridge to the left side in
leftiminutes. - Put the box into the left warehouse in
putiminutes.
The i^th worker is less efficient than the j^th worker if either condition is met:
lefti + righti > leftj + rightjlefti + righti == leftj + rightjandi > j
The following rules regulate the movement of the workers through the bridge:
- Only one worker can use the bridge at a time.
- When the bridge is unused, prioritize the least efficient worker who has picked up a box on the right side to cross; if none exists, prioritize the least efficient worker on the left side to cross.
- If enough workers have already been dispatched from the left side to pick up all the remaining boxes, no more workers will be sent from the left side.
Return the elapsed minutes at which the last box reaches the left side of the bridge.
Example 1
Input
n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]Output
6Worker 2 crosses to the right, picks up the only box, and returns to the left side at minute 6, so the last box reaches the left side then.
Example 2
Input
n = 3, k = 2, time = [[1,5,1,8],[10,10,10,10]]Output
37The last box reaches the left side at 37 seconds, and the last boxes do not need to be put down because they are already on the left with the workers.
Constraints
- 1 <= n, k <= 10^4
- time.length == k
- time[i].length == 4
- 1 <= lefti, picki, righti, puti <= 1000