Time to Cross a Bridge

Hard

#2312Time: O(T * k * log k), where `T` is the final completion time. `T` can be very large (e.g., `n` times the average cycle time). At each time step, we might need to iterate through and sort the `k` workers, making this approach too slow for the given constraints.Space: O(k), to store the state of each of the `k` workers.1 company

Data structures

Array Heap (Priority Queue)

Companies

Prompt

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] = [right_i, pick_i, left_i, put_i].

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 right_i minutes.
Pick a box from the right warehouse in pick_i minutes.
Cross the bridge to the left side in left_i minutes.
Put the box into the left warehouse in put_i minutes.

The i^th worker is less efficient than the j^th worker if either condition is met:

left_i + right_i > left_j + right_j
left_i + right_i == left_j + right_j and i > 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 have picked up the box) on the right side to cross. If not, 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: 6

Explanation:

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:

Input: n = 3, k = 2, time = [[1,5,1,8],[10,10,10,10]]

Output: 37

Explanation:

The last box reaches the left side at 37 seconds. Notice, how we do not put the last boxes down, as that would take more time, and they are already on the left with the workers.

Constraints:

1 <= n, k <= 10⁴
time.length == k
time[i].length == 4
1 <= left_i, pick_i, right_i, put_i <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the process by incrementing time one unit at a time. At each time step, it checks the status of all workers and the bridge to see if any state changes occur. This method is straightforward to conceptualize but is computationally expensive.

Algorithm

Initialize currentTime = 0, worker states (location, task, finish time), boxes_to_move = n, boxes_delivered = 0.
Create lists or arrays to represent workers waiting on the left and right sides.
Start a loop that continues as long as boxes_delivered < n.
Inside the loop, for the current currentTime: a. Iterate through all k workers. If a worker's task was scheduled to finish at currentTime, update their status (e.g., from 'picking' to 'waiting on right'). b. Check if the bridge is free (i.e., currentTime is greater than or equal to the time the last crossing ends). c. If the bridge is free, determine who crosses next: i. Check the list of workers waiting on the right. If not empty, find the one with the highest priority (least efficient) and dispatch them. ii. If no one from the right crosses, check the list of workers waiting on the left. If not empty and more boxes need to be moved, find the highest priority worker and dispatch them. iii. When a worker is dispatched, update their state to 'crossing', calculate their arrival time, and set the bridge's busy-until time. d. Increment currentTime by 1.
The simulation ends when the n-th box reaches the left side of the bridge. Return the currentTime of that event.

Walkthrough

In this method, we maintain the state of each worker, including their location (left/right), their current task (waiting, crossing, picking, putting), and the time they will finish their current task. We also track the state of the bridge (busy/free) and until when it's busy. The simulation proceeds in a loop, incrementing a currentTime variable from 0 upwards. In each iteration, we check all workers to see if they have completed their tasks. If the bridge is free, we apply the given priority rules to select a worker from the waiting queues (first from the right, then from the left). The selected worker begins crossing, and their state is updated accordingly. This continues until n boxes have reached the left side of the bridge.

Complexity

Time

O(T * k * log k), where `T` is the final completion time. `T` can be very large (e.g., `n` times the average cycle time). At each time step, we might need to iterate through and sort the `k` workers, making this approach too slow for the given constraints.

Space

O(k), to store the state of each of the `k` workers.

Trade-offs

Pros

Conceptually simple and easy to understand.

Cons

Extremely inefficient for the given constraints. The total simulation time can be very large, leading to a 'Time Limit Exceeded' error.
The complexity is proportional to the total elapsed time, which is not ideal for problems with large time values.

Solutions

Solution

1class Solution {2public3  int findCrossingTime(int n, int k, int[][] time) {4    int[][] t = new int[k][5];5    for (int i = 0; i < k; ++i) {6      int[] x = time[i];7      t[i] = new int[]{x[0], x[1], x[2], x[3], i};8    }9    Arrays.sort(10        t, (a, b)->{11          int x = a[0] + a[2], y = b[0] + b[2];12          return x == y ? a[4] - b[4] : x - y;13        });14    int cur = 0;15    PriorityQueue<Integer> waitInLeft = new PriorityQueue<>((a, b)->b - a);16    PriorityQueue<Integer> waitInRight = new PriorityQueue<>((a, b)->b - a);17    PriorityQueue<int[]> workInLeft = new PriorityQueue<>((a, b)->a[0] - b[0]);18    PriorityQueue<int[]> workInRight = new PriorityQueue<>((a, b)->a[0] - b[0]);19    for (int i = 0; i < k; ++i) {20      waitInLeft.offer(i);21    }22    while (true) {23      while (!workInLeft.isEmpty()) {24        int[] p = workInLeft.peek();25        if (p[0] > cur) {26          break;27        }28        waitInLeft.offer(workInLeft.poll()[1]);29      }30      while (!workInRight.isEmpty()) {31        int[] p = workInRight.peek();32        if (p[0] > cur) {33          break;34        }35        waitInRight.offer(workInRight.poll()[1]);36      }37      boolean leftToGo = n > 0 && !waitInLeft.isEmpty();38      boolean rightToGo = !waitInRight.isEmpty();39      if (!leftToGo && !rightToGo) {40        int nxt = 1 << 30;41        if (!workInLeft.isEmpty()) {42          nxt = Math.min(nxt, workInLeft.peek()[0]);43        }44        if (!workInRight.isEmpty()) {45          nxt = Math.min(nxt, workInRight.peek()[0]);46        }47        cur = nxt;48        continue;49      }50      if (rightToGo) {51        int i = waitInRight.poll();52        cur += t[i][2];53        if (n == 0 && waitInRight.isEmpty() && workInRight.isEmpty()) {54          return cur;55        }56        workInLeft.offer(new int[]{cur + t[i][3], i});57      } else {58        int i = waitInLeft.poll();59        cur += t[i][0];60        --n;61        workInRight.offer(new int[]{cur + t[i][1], i});62      }63    }64  }65}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem