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.
C++
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.
C#
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.
| 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. |
| 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 |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,667 views views
Watch 9 more video solutions →Practice Time to Cross a Bridge with our built-in code editor and test cases.
Practice on FleetCode