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.
In this approach, we use a priority queue to determine which worker should use the bridge next. We prioritize the least efficient worker based on the rules provided. Each worker has a cost to cross the bridge to the right and to the left, and we need to manage these costs efficiently using the priority queue.
Python Explanation:
In this Python solution, we start by defining a Worker class to keep track of each worker's times and index. We sort workers by their total crossing time (left + right) and prioritize the least efficient ones first when idle. We use two priority queues: one for workers on the left who can cross to the right, and one for workers who have picked boxes on the right to return left. The loop continues until all boxes are moved, updating the elapsed time accordingly.
Time Complexity: O(n log k), where n is the number of boxes and k is the number of workers, due to the sorting and priority queue operations.
Space Complexity: O(k), the space needed for the priority queues.
This approach employs a greedy strategy to choose the optimal worker to cross the bridge at any given time. Instead of managing a priority queue, it directly applies logic to choose the least efficient worker in line with the problem's requirements.
Java Explanation:
In this Java solution, we define a Worker class implementing Comparable to define the logic for sorting and prioritizing workers based on their crossing times. We sort workers initially and then use two priority queues to select the optimal movements for workers. The elapsed time is adjusted dynamically to ensure efficient movement of all boxes.
Time Complexity: O(n log k), as sorting the workers and managing the priority queues are the main operations.
Space Complexity: O(k), for storing worker data in priority queues.
First, we sort the workers by efficiency in descending order, so the worker with the highest index has the lowest efficiency.
Next, we use four priority queues to simulate the state of the workers:
wait_in_left: Max-heap, storing the indices of workers currently waiting on the left bank;wait_in_right: Max-heap, storing the indices of workers currently waiting on the right bank;work_in_left: Min-heap, storing the time when workers currently working on the left bank finish placing boxes and the indices of the workers;work_in_right: Min-heap, storing the time when workers currently working on the right bank finish picking up boxes and the indices of the workers.Initially, all workers are on the left bank, so wait_in_left stores the indices of all workers. We use the variable cur to record the current time.
Then, we simulate the entire process. First, we check if any worker in work_in_left has finished placing boxes at the current time. If so, we move the worker to wait_in_left and remove the worker from work_in_left. Similarly, we check if any worker in work_in_right has finished picking up boxes. If so, we move the worker to wait_in_right and remove the worker from work_in_right.
Next, we check if there are any workers waiting on the left bank at the current time, denoted as left_to_go. At the same time, we check if there are any workers waiting on the right bank, denoted as right_to_go. If there are no workers waiting to cross the river, we directly update cur to the next time when a worker finishes placing boxes and continue the simulation.
If right_to_go is true, we take a worker from wait_in_right, update cur to the current time plus the time it takes for the worker to cross from the right bank to the left bank. If all workers have crossed to the right bank at this point, we directly return cur as the answer; otherwise, we move the worker to work_in_left.
If left_to_go is true, we take a worker from wait_in_left, update cur to the current time plus the time it takes for the worker to cross from the left bank to the right bank, then move the worker to work_in_right and decrement the number of boxes.
Repeat the above process until the number of boxes is zero. At this point, cur is the answer.
The time complexity is O(n times log k), and the space complexity is O(k). Here, n and k are the number of workers and the number of boxes, respectively.
| Approach | Complexity |
|---|---|
| Priority Queue for Least Efficient Worker | Time Complexity: O(n log k), where n is the number of boxes and k is the number of workers, due to the sorting and priority queue operations. Space Complexity: O(k), the space needed for the priority queues. |
| Greedy Strategy for Optimal Worker Selection | Time Complexity: O(n log k), as sorting the workers and managing the priority queues are the main operations. Space Complexity: O(k), for storing worker data in priority queues. |
| Priority Queue (Max-Heap and Min-Heap) + Simulation | — |
| 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 |
2532. Time to Cross a Bridge (Leetcode Hard) • Programming Live with Larry • 1,092 views views
Watch 7 more video solutions →Practice Time to Cross a Bridge with our built-in code editor and test cases.
Practice on FleetCode