Time to Cross a Bridge - Video Solutions
2532. Time to Cross a Bridge (Leetcode Hard)
Time to Cross a Bridge - Video Solution
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,103 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- 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 ith worker is less efficient than the jth 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 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 <= 104time.length == ktime[i].length == 41 <= lefti, picki, righti, puti <= 1000
Approach Overview
Problem 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.
Complexity Analysis
| 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 |