Watch 8 video solutions for Time to Cross a Bridge, a hard level problem involving Array, Heap (Priority Queue), Simulation. This walkthrough by Programming Live with Larry has 1,092 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
righti minutes.picki minutes.lefti minutes.puti minutes.The ith worker is less efficient than the jth worker if either condition is met:
lefti + righti > leftj + rightjlefti + righti == leftj + rightj and i > jThe 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.
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 <= 104time.length == ktime[i].length == 41 <= lefti, picki, righti, puti <= 1000Problem Overview: You manage workers moving k boxes from the right bank of a bridge to the left bank. Each worker has four times: crossing left→right, picking a box, crossing right→left, and putting the box down. Only one worker can be on the bridge at a time, so you must schedule workers carefully to minimize the total time required to move all boxes.
Approach 1: Priority Queue for Least Efficient Worker (O((n + k) log n) time, O(n) space)
This approach simulates the entire process using multiple priority queues. Workers waiting on either side of the bridge are stored in max-heaps ordered by efficiency score (leftToRight + rightToLeft). Less efficient workers get priority because sending them earlier prevents them from becoming a bottleneck later. Two additional min-heaps track workers currently busy picking up or putting down boxes, ordered by the time they become available.
At each step, advance the simulation clock and move workers between queues as they finish tasks. If a worker is waiting on the right side, they cross back first since they already hold a box. Otherwise, send the next worker from the left side to fetch a box. This structure ensures the bridge is always used optimally while respecting worker availability and timing constraints. The method relies heavily on simulation and efficient heap operations.
Approach 2: Greedy Strategy for Optimal Worker Selection (O((n + k) log n) time, O(n) space)
The greedy solution follows the same simulation idea but frames the decision making explicitly as a scheduling strategy. At any moment, prioritize workers on the right bank since they already carry a box and must return. If none are waiting, choose a worker from the left bank using a greedy rule: send the worker with the highest crossing cost first. This ordering reduces idle bridge time later because slower workers start their long trips earlier.
Data structures still rely on heaps for efficient worker selection and availability tracking. Arrays store worker timings, while priority queues maintain ordering by efficiency and next available time. Each event—crossing, picking, or placing—updates the simulation state until all k boxes reach the left side. The greedy interpretation simply clarifies why the ordering rule produces the optimal schedule.
Recommended for interviews: The priority queue simulation is what interviewers usually expect. It demonstrates mastery of array data handling, heap-based scheduling, and event-driven simulation. A brute-force simulation without heaps quickly becomes inefficient. Showing the heap-based scheduling pattern proves you can manage complex state transitions efficiently.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Priority Queue Simulation | O((n + k) log n) | O(n) | General optimal solution for scheduling workers and tracking availability efficiently |
| Greedy Worker Scheduling with Heaps | O((n + k) log n) | O(n) | When reasoning about optimal ordering of slower workers first |