Facebook Pixel

2532. Time to Cross a Bridge

HardArraySimulationHeap (Priority Queue)
Leetcode Link

Problem Description

This problem simulates workers moving boxes across a bridge between two warehouses. You have n boxes that need to be moved from the right (old) warehouse to the left (new) warehouse by k workers.

Each worker i has four time attributes given in time[i] = [right_i, pick_i, left_i, put_i]:

  • right_i: Time to cross the bridge from left to right
  • pick_i: Time to pick up a box from the right warehouse
  • left_i: Time to cross the bridge from right to left
  • put_i: Time to put down a box in the left warehouse

The complete cycle for a worker to move one box involves:

  1. Cross bridge to the right side (right_i minutes)
  2. Pick up a box (pick_i minutes)
  3. Cross bridge back to the left side (left_i minutes)
  4. Put down the box (put_i minutes)

Worker Efficiency Rules: Worker i is less efficient than worker j if:

  • left_i + right_i > left_j + right_j, OR
  • left_i + right_i == left_j + right_j AND i > j

In other words, workers are ranked by their total bridge crossing time, with ties broken by worker index.

Bridge Usage Rules:

  1. Only one worker can use the bridge at any time
  2. When multiple workers are waiting to cross:
    • Prioritize workers on the right side (carrying boxes) over workers on the left side
    • Among workers on the same side, the least efficient worker crosses first
  3. Workers stop being sent from the left side once enough workers have been dispatched to handle all remaining boxes

Initial Setup:

  • All k workers start on the left side of the bridge
  • All n boxes are in the right warehouse

The goal is to find the total time when the last box reaches the left warehouse (i.e., when the last worker carrying a box finishes crossing the bridge from right to left).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that this is an event-driven simulation problem where workers transition between different states: waiting to cross, crossing the bridge, and working in warehouses.

Since only one worker can use the bridge at a time, the bridge becomes a bottleneck. We need to track which workers are available to cross at any given moment and choose the right one based on the priority rules.

The problem has four distinct states for workers:

  1. Waiting on the left to go pick up boxes
  2. Working on the right (picking up a box)
  3. Waiting on the right to return with a box
  4. Working on the left (putting down a box)

Workers move through these states in a cycle: wait left → cross → work right → wait right → cross → work left → wait left.

The priority rules tell us we need to:

  • Always let workers with boxes (on the right) cross before empty-handed workers (on the left)
  • Among workers on the same side, let the least efficient one cross first

Since "least efficient" means highest crossing time (or highest index as tiebreaker), we can use max-heaps to automatically get the least efficient worker when needed. We use negative indices in Python's min-heap to simulate a max-heap.

For workers who are currently working (not waiting), we need to know when they'll finish. This is a time-based event, so we use min-heaps to track the earliest completion time.

The simulation advances by:

  1. Moving any workers who finished their warehouse work to the waiting queues
  2. Checking if anyone is waiting to cross
  3. If someone is waiting, let the appropriate worker cross based on priorities
  4. If no one is waiting, jump forward in time to when the next worker finishes their warehouse work

The clever optimization is sorting workers by efficiency first. This way, worker indices naturally represent efficiency rankings, making heap operations straightforward.

The simulation ends when all boxes have been moved and the last worker carrying a box crosses to the left side. We track this by checking if n == 0 (all boxes assigned) and no workers remain on the right side.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The implementation uses priority queues and simulation to track worker movements across the bridge.

Initial Setup: First, we sort the workers by their efficiency metric left[i] + right[i] in ascending order. This clever preprocessing means that worker index i directly represents their efficiency ranking - higher index means less efficient.

time.sort(key=lambda x: x[0] + x[2])

Data Structures: We maintain four priority queues to track worker states:

  • wait_in_left: Max-heap storing indices of workers waiting on the left bank (use negative indices to simulate max-heap)
  • wait_in_right: Max-heap storing indices of workers waiting on the right bank
  • work_in_left: Min-heap storing (finish_time, worker_index) for workers putting boxes in left warehouse
  • work_in_right: Min-heap storing (finish_time, worker_index) for workers picking boxes in right warehouse

Initially, all workers are waiting on the left:

for i in range(k):
    heappush(wait_in_left, -i)

Simulation Loop: The main simulation uses cur to track current time and processes events:

  1. Update waiting queues: Check if any workers have finished their warehouse work at current time

    while work_in_left and work_in_left[0][0] <= cur:
    t, i = heappop(work_in_left)
    heappush(wait_in_left, -i)

    Similar logic applies for work_in_right.

  2. Determine crossing eligibility:

    • left_to_go = n > 0 and wait_in_left: Workers can go from left only if boxes remain
    • right_to_go = bool(wait_in_right): Workers on right always need to return

  3. Handle no waiting workers: If nobody is waiting to cross, fast-forward time to next worker completion

    if not left_to_go and not right_to_go:
    nxt = min(work_in_left[0][0], work_in_right[0][0])
    cur = nxt

  4. Process bridge crossing with priorities:

    • Right side has priority (carrying boxes):

      i = -heappop(wait_in_right)  # Get least efficient worker
cur += time[i][2]  # Add crossing time
heappush(work_in_left, (cur + time[i][3], i))  # Schedule put completion

      Check termination: if n == 0 and no workers remain on right, return cur

    • Left side crossing (going to pick boxes):

      i = -heappop(wait_in_left)
cur += time[i][0]  # Add crossing time
n -= 1  # One box assigned
heappush(work_in_right, (cur + time[i][1], i))  # Schedule pick completion

The simulation continues until all boxes are moved. The answer is the time when the last worker carrying a box finishes crossing to the left, which is captured by the termination condition when n == 0 and both wait_in_right and work_in_right are empty.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with n = 3 boxes and k = 2 workers:

  • Worker 0: [1, 1, 2, 1] (right=1, pick=1, left=2, put=1)
  • Worker 1: [1, 2, 3, 1] (right=1, pick=2, left=3, put=1)

Step 1: Sort workers by efficiency

  • Worker 0: total crossing time = 1 + 2 = 3
  • Worker 1: total crossing time = 1 + 3 = 4
  • After sorting: Worker 0 stays at index 0, Worker 1 at index 1 (Worker 1 is less efficient)

Step 2: Initialize data structures

  • cur = 0 (current time)
  • wait_in_left = [-1, -0] (both workers waiting on left, -1 has priority as least efficient)
  • wait_in_right = [] (empty)
  • work_in_left = [] (empty)
  • work_in_right = [] (empty)

Step 3: Simulation begins

Time 0:

  • Check workers: No one finished working yet
  • Can go left→right? Yes (n=3 > 0 and workers waiting)
  • Can go right→left? No (no one waiting on right)
  • Worker 1 (least efficient) crosses left→right
  • cur = 0 + 1 = 1 (crossing time)
  • Worker 1 starts picking at time 1, finishes at time 3
  • work_in_right = [(3, 1)]
  • n = 2 (one box assigned)

Time 1:

  • Check workers: No one finished working yet
  • Can go left→right? Yes (n=2 > 0 and worker 0 waiting)
  • Can go right→left? No (no one waiting on right)
  • Worker 0 crosses left→right
  • cur = 1 + 1 = 2 (crossing time)
  • Worker 0 starts picking at time 2, finishes at time 3
  • work_in_right = [(3, 1), (3, 0)]
  • n = 1 (another box assigned)

Time 2:

  • No one waiting to cross
  • Fast-forward to next event at time 3

Time 3:

  • Workers 0 and 1 finish picking
  • wait_in_right = [-1, -0] (both ready to return, -1 has priority)
  • Can go right→left? Yes
  • Worker 1 (least efficient) crosses right→left with box
  • cur = 3 + 3 = 6 (crossing time)
  • Worker 1 starts putting at time 6, finishes at time 7
  • work_in_left = [(7, 1)]

Time 6:

  • Worker 0 still waiting on right
  • Can go right→left? Yes
  • Worker 0 crosses right→left with box
  • cur = 6 + 2 = 8 (crossing time)
  • Worker 0 starts putting at time 8, finishes at time 9
  • work_in_left = [(7, 1), (9, 0)]

Time 8:

  • Worker 1 finishes putting at time 7 (already passed)
  • wait_in_left = [-1] (worker 1 back on left)
  • Can go left→right? Yes (n=1 > 0)
  • Worker 1 crosses left→right
  • cur = 8 + 1 = 9
  • Worker 1 starts picking at time 9, finishes at time 11
  • work_in_right = [(11, 1)]
  • n = 0 (last box assigned)

Time 9:

  • Worker 0 finishes putting
  • wait_in_left = [-0]
  • Can go left→right? No (n=0, no more boxes)
  • Fast-forward to time 11

Time 11:

  • Worker 1 finishes picking last box
  • wait_in_right = [-1]
  • Worker 1 crosses right→left with final box
  • cur = 11 + 3 = 14
  • Check termination: n=0 and no workers remain on right
  • Return 14 (time when last box reaches left warehouse)

The simulation successfully tracks all worker movements and correctly identifies that the last box reaches the left warehouse at time 14, when Worker 1 completes their final crossing.

Solution Implementation

1class Solution:
2    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:
3        """
4        Find the time when the last box reaches the right side.
5      
6        Args:
7            n: Number of boxes to transport
8            k: Number of workers
9            time: List of [leftToRight, pickOld, rightToLeft, putNew] times for each worker
10      
11        Returns:
12            Time when the last box arrives at the right side
13        """
14        from heapq import heappush, heappop
15        from math import inf
16      
17        # Sort workers by their efficiency (less efficient workers have higher priority)
18        # This ensures less efficient workers get priority when multiple are waiting
19        time.sort(key=lambda x: x[0] + x[2])
20      
21        current_time = 0
22      
23        # Priority queues for workers waiting on each side (negative index for max-heap)
24        waiting_left = []  # Workers waiting on left side
25        waiting_right = []  # Workers waiting on right side
26      
27        # Priority queues for workers currently working on each side
28        # Format: (finish_time, worker_index)
29        working_left = []  # Workers picking/putting boxes on left side
30        working_right = []  # Workers picking/putting boxes on right side
31      
32        # Initially, all workers are waiting on the left side
33        for worker_id in range(k):
34            heappush(waiting_left, -worker_id)
35      
36        while True:
37            # Move workers who finished their work to waiting queues
38            # Check left side workers
39            while working_left:
40                finish_time, worker_id = working_left[0]
41                if finish_time > current_time:
42                    break
43                heappop(working_left)
44                heappush(waiting_left, -worker_id)
45          
46            # Check right side workers
47            while working_right:
48                finish_time, worker_id = working_right[0]
49                if finish_time > current_time:
50                    break
51                heappop(working_right)
52                heappush(waiting_right, -worker_id)
53          
54            # Determine if there are workers ready to cross
55            can_cross_from_left = n > 0 and waiting_left  # Still boxes to move and workers available
56            can_cross_from_right = bool(waiting_right)  # Workers waiting on right side
57          
58            # If no one can cross right now, advance time to next event
59            if not can_cross_from_left and not can_cross_from_right:
60                next_event_time = inf
61              
62                if working_left:
63                    next_event_time = min(next_event_time, working_left[0][0])
64                if working_right:
65                    next_event_time = min(next_event_time, working_right[0][0])
66              
67                current_time = next_event_time
68                continue
69          
70            # Priority: workers on right side cross first (to free up space)
71            if can_cross_from_right:
72                # Get the least efficient worker (highest priority in our max-heap)
73                worker_id = -heappop(waiting_right)
74              
75                # Worker crosses from right to left
76                current_time += time[worker_id][2]  # rightToLeft time
77              
78                # Check if this was the last box being delivered
79                if n == 0 and not waiting_right and not working_right:
80                    return current_time
81              
82                # Worker starts putting the box on the left side
83                finish_time = current_time + time[worker_id][3]  # putNew time
84                heappush(working_left, (finish_time, worker_id))
85            else:
86                # Worker crosses from left to right with a box
87                worker_id = -heappop(waiting_left)
88              
89                # Worker crosses from left to right
90                current_time += time[worker_id][0]  # leftToRight time
91                n -= 1  # One box is being transported
92              
93                # Worker starts picking up the box on the right side
94                finish_time = current_time + time[worker_id][1]  # pickOld time
95                heappush(working_right, (finish_time, worker_id))
96
1class Solution {
2    public int findCrossingTime(int n, int k, int[][] time) {
3        // Create extended array to store worker info with index
4        // Format: [leftToRight, pickOld, rightToLeft, putNew, originalIndex]
5        int[][] workers = new int[k][5];
6        for (int i = 0; i < k; ++i) {
7            int[] workerTime = time[i];
8            workers[i] = new int[] {
9                workerTime[0],  // time to cross bridge from left to right
10                workerTime[1],  // time to pick up box at right warehouse
11                workerTime[2],  // time to cross bridge from right to left
12                workerTime[3],  // time to put down box at left warehouse
13                i               // original worker index
14            };
15        }
16      
17        // Sort workers by efficiency (less efficient workers have higher priority)
18        // Efficiency = time to cross bridge (leftToRight + rightToLeft)
19        // If equal efficiency, prefer worker with smaller index
20        Arrays.sort(workers, (a, b) -> {
21            int efficiencyA = a[0] + a[2];
22            int efficiencyB = b[0] + b[2];
23            return efficiencyA == efficiencyB ? a[4] - b[4] : efficiencyA - efficiencyB;
24        });
25      
26        int currentTime = 0;
27      
28        // Priority queues for workers waiting on each side (max heap by efficiency index)
29        PriorityQueue<Integer> waitingOnLeft = new PriorityQueue<>((a, b) -> b - a);
30        PriorityQueue<Integer> waitingOnRight = new PriorityQueue<>((a, b) -> b - a);
31      
32        // Priority queues for workers working on each side (min heap by finish time)
33        // Format: [finishTime, workerIndex]
34        PriorityQueue<int[]> workingOnLeft = new PriorityQueue<>((a, b) -> a[0] - b[0]);
35        PriorityQueue<int[]> workingOnRight = new PriorityQueue<>((a, b) -> a[0] - b[0]);
36      
37        // Initially all workers are waiting on the left side
38        for (int i = 0; i < k; ++i) {
39            waitingOnLeft.offer(i);
40        }
41      
42        while (true) {
43            // Move workers who finished working on left side to waiting queue
44            while (!workingOnLeft.isEmpty()) {
45                int[] worker = workingOnLeft.peek();
46                if (worker[0] > currentTime) {
47                    break;
48                }
49                waitingOnLeft.offer(workingOnLeft.poll()[1]);
50            }
51          
52            // Move workers who finished working on right side to waiting queue
53            while (!workingOnRight.isEmpty()) {
54                int[] worker = workingOnRight.peek();
55                if (worker[0] > currentTime) {
56                    break;
57                }
58                waitingOnRight.offer(workingOnRight.poll()[1]);
59            }
60          
61            // Check if there are workers ready to cross the bridge
62            boolean canCrossFromLeft = n > 0 && !waitingOnLeft.isEmpty();
63            boolean canCrossFromRight = !waitingOnRight.isEmpty();
64          
65            // If no one can cross, advance time to next event
66            if (!canCrossFromLeft && !canCrossFromRight) {
67                int nextEventTime = Integer.MAX_VALUE;
68                if (!workingOnLeft.isEmpty()) {
69                    nextEventTime = Math.min(nextEventTime, workingOnLeft.peek()[0]);
70                }
71                if (!workingOnRight.isEmpty()) {
72                    nextEventTime = Math.min(nextEventTime, workingOnRight.peek()[0]);
73                }
74                currentTime = nextEventTime;
75                continue;
76            }
77          
78            // Priority: workers on right side cross first (carrying boxes back)
79            if (canCrossFromRight) {
80                int workerIndex = waitingOnRight.poll();
81                currentTime += workers[workerIndex][2];  // add bridge crossing time (right to left)
82              
83                // Check if this is the last box being delivered
84                if (n == 0 && waitingOnRight.isEmpty() && workingOnRight.isEmpty()) {
85                    return currentTime;
86                }
87              
88                // Worker starts putting down box on left side
89                workingOnLeft.offer(new int[] {
90                    currentTime + workers[workerIndex][3],  // finish time
91                    workerIndex
92                });
93            } else {
94                // Worker crosses from left to right
95                int workerIndex = waitingOnLeft.poll();
96                currentTime += workers[workerIndex][0];  // add bridge crossing time (left to right)
97                n--;  // one less box to move
98              
99                // Worker starts picking up box on right side
100                workingOnRight.offer(new int[] {
101                    currentTime + workers[workerIndex][1],  // finish time
102                    workerIndex
103                });
104            }
105        }
106    }
107}
108
1class Solution {
2public:
3    int findCrossingTime(int n, int k, vector<vector<int>>& time) {
4        // Pair type for storing (time, worker_index)
5        using TimeworkerPair = pair<int, int>;
6      
7        // Add worker index to each time array for tracking
8        for (int i = 0; i < k; ++i) {
9            time[i].push_back(i);
10        }
11      
12        // Sort workers by efficiency (less efficient workers have higher priority)
13        // Efficiency is measured by total bridge crossing time (leftToRight + rightToLeft)
14        sort(time.begin(), time.end(), [](auto& a, auto& b) {
15            int totalTimeA = a[0] + a[2];  // leftToRight + rightToLeft for worker A
16            int totalTimeB = b[0] + b[2];  // leftToRight + rightToLeft for worker B
17            // If total time is same, compare by original index (lower index = higher priority)
18            return totalTimeA == totalTimeB ? a[4] < b[4] : totalTimeA < totalTimeB;
19        });
20      
21        int currentTime = 0;
22      
23        // Priority queues for workers waiting on each side (max heap by worker efficiency)
24        priority_queue<int> waitingOnLeft, waitingOnRight;
25      
26        // Priority queues for workers working on each side (min heap by completion time)
27        priority_queue<TimeworkerPair, vector<TimeworkerPair>, greater<TimeworkerPair>> workingOnLeft, workingOnRight;
28      
29        // Initially, all workers are waiting on the left side
30        for (int i = 0; i < k; ++i) {
31            waitingOnLeft.push(i);
32        }
33      
34        while (true) {
35            // Move workers who finished working on left side to waiting queue
36            while (!workingOnLeft.empty()) {
37                auto [finishTime, workerIdx] = workingOnLeft.top();
38                if (finishTime > currentTime) {
39                    break;
40                }
41                workingOnLeft.pop();
42                waitingOnLeft.push(workerIdx);
43            }
44          
45            // Move workers who finished working on right side to waiting queue
46            while (!workingOnRight.empty()) {
47                auto [finishTime, workerIdx] = workingOnRight.top();
48                if (finishTime > currentTime) {
49                    break;
50                }
51                workingOnRight.pop();
52                waitingOnRight.push(workerIdx);
53            }
54          
55            // Check if there are workers ready to cross the bridge
56            bool canCrossFromLeft = n > 0 && !waitingOnLeft.empty();   // Still boxes to move
57            bool canCrossFromRight = !waitingOnRight.empty();
58          
59            // If no one can cross, advance time to next event
60            if (!canCrossFromLeft && !canCrossFromRight) {
61                int nextEventTime = 1 << 30;  // Large value as initial minimum
62              
63                if (!workingOnLeft.empty()) {
64                    nextEventTime = min(nextEventTime, workingOnLeft.top().first);
65                }
66                if (!workingOnRight.empty()) {
67                    nextEventTime = min(nextEventTime, workingOnRight.top().first);
68                }
69              
70                currentTime = nextEventTime;
71                continue;
72            }
73          
74            // Priority: workers on right side cross first (bringing boxes back)
75            if (canCrossFromRight) {
76                int workerIdx = waitingOnRight.top();
77                waitingOnRight.pop();
78              
79                // Worker crosses from right to left
80                currentTime += time[workerIdx][2];  // Add rightToLeft crossing time
81              
82                // Check if all boxes have been moved
83                if (n == 0 && waitingOnRight.empty() && workingOnRight.empty()) {
84                    return currentTime;
85                }
86              
87                // Worker starts working on left side (putting box in old warehouse)
88                workingOnLeft.push({currentTime + time[workerIdx][3], workerIdx});
89            } else {
90                // Worker crosses from left to right
91                int workerIdx = waitingOnLeft.top();
92                waitingOnLeft.pop();
93              
94                currentTime += time[workerIdx][0];  // Add leftToRight crossing time
95                --n;  // One less box to move
96              
97                // Worker starts working on right side (picking up box from new warehouse)
98                workingOnRight.push({currentTime + time[workerIdx][1], workerIdx});
99            }
100        }
101    }
102};
103
1function findCrossingTime(n: number, k: number, time: number[][]): number {
2    // Add worker index to each time array for tracking
3    for (let i = 0; i < k; i++) {
4        time[i].push(i);
5    }
6  
7    // Sort workers by efficiency (less efficient workers have higher priority)
8    // Efficiency is measured by total bridge crossing time (leftToRight + rightToLeft)
9    time.sort((a, b) => {
10        const totalTimeA = a[0] + a[2];  // leftToRight + rightToLeft for worker A
11        const totalTimeB = b[0] + b[2];  // leftToRight + rightToLeft for worker B
12        // If total time is same, compare by original index (lower index = higher priority)
13        return totalTimeA === totalTimeB ? a[4] - b[4] : totalTimeA - totalTimeB;
14    });
15  
16    let currentTime = 0;
17  
18    // Priority queues for workers waiting on each side (max heap by worker efficiency)
19    // In TypeScript, we'll use arrays with custom sorting for priority queues
20    const waitingOnLeft: number[] = [];
21    const waitingOnRight: number[] = [];
22  
23    // Priority queues for workers working on each side (min heap by completion time)
24    // Store as [finishTime, workerIndex] tuples
25    const workingOnLeft: [number, number][] = [];
26    const workingOnRight: [number, number][] = [];
27  
28    // Helper function to maintain max heap property (higher index = higher priority)
29    const insertMaxHeap = (heap: number[], value: number): void => {
30        heap.push(value);
31        heap.sort((a, b) => b - a);
32    };
33  
34    // Helper function to maintain min heap property for working queues
35    const insertMinHeap = (heap: [number, number][], value: [number, number]): void => {
36        heap.push(value);
37        heap.sort((a, b) => a[0] - b[0]);
38    };
39  
40    // Initially, all workers are waiting on the left side
41    for (let i = 0; i < k; i++) {
42        insertMaxHeap(waitingOnLeft, i);
43    }
44  
45    while (true) {
46        // Move workers who finished working on left side to waiting queue
47        while (workingOnLeft.length > 0) {
48            const [finishTime, workerIdx] = workingOnLeft[0];
49            if (finishTime > currentTime) {
50                break;
51            }
52            workingOnLeft.shift();  // Remove from front (min element)
53            insertMaxHeap(waitingOnLeft, workerIdx);
54        }
55      
56        // Move workers who finished working on right side to waiting queue
57        while (workingOnRight.length > 0) {
58            const [finishTime, workerIdx] = workingOnRight[0];
59            if (finishTime > currentTime) {
60                break;
61            }
62            workingOnRight.shift();  // Remove from front (min element)
63            insertMaxHeap(waitingOnRight, workerIdx);
64        }
65      
66        // Check if there are workers ready to cross the bridge
67        const canCrossFromLeft = n > 0 && waitingOnLeft.length > 0;  // Still boxes to move
68        const canCrossFromRight = waitingOnRight.length > 0;
69      
70        // If no one can cross, advance time to next event
71        if (!canCrossFromLeft && !canCrossFromRight) {
72            let nextEventTime = Number.MAX_SAFE_INTEGER;  // Large value as initial minimum
73          
74            if (workingOnLeft.length > 0) {
75                nextEventTime = Math.min(nextEventTime, workingOnLeft[0][0]);
76            }
77            if (workingOnRight.length > 0) {
78                nextEventTime = Math.min(nextEventTime, workingOnRight[0][0]);
79            }
80          
81            currentTime = nextEventTime;
82            continue;
83        }
84      
85        // Priority: workers on right side cross first (bringing boxes back)
86        if (canCrossFromRight) {
87            const workerIdx = waitingOnRight.shift()!;  // Remove highest priority worker
88          
89            // Worker crosses from right to left
90            currentTime += time[workerIdx][2];  // Add rightToLeft crossing time
91          
92            // Check if all boxes have been moved
93            if (n === 0 && waitingOnRight.length === 0 && workingOnRight.length === 0) {
94                return currentTime;
95            }
96          
97            // Worker starts working on left side (putting box in old warehouse)
98            insertMinHeap(workingOnLeft, [currentTime + time[workerIdx][3], workerIdx]);
99        } else {
100            // Worker crosses from left to right
101            const workerIdx = waitingOnLeft.shift()!;  // Remove highest priority worker
102          
103            currentTime += time[workerIdx][0];  // Add leftToRight crossing time
104            n--;  // One less box to move
105          
106            // Worker starts working on right side (picking up box from new warehouse)
107            insertMinHeap(workingOnRight, [currentTime + time[workerIdx][1], workerIdx]);
108        }
109    }
110}
111

Time and Space Complexity

Time Complexity: O(n × log k)

The algorithm processes each of the n boxes exactly once. For each box:

  • A worker is selected from the waiting queue (either wait_in_left or wait_in_right) using heap operations: O(log k)
  • The worker is then added to a work queue (work_in_left or work_in_right) using heap operations: O(log k)
  • Workers are moved from work queues back to waiting queues using heap operations: O(log k)

Since each box requires a constant number of heap operations and there are n boxes to process, the total time complexity is O(n × log k).

Space Complexity: O(k)

The algorithm maintains four heaps:

  • wait_in_left: stores indices of workers waiting on the left bank, at most k workers
  • wait_in_right: stores indices of workers waiting on the right bank, at most k workers
  • work_in_left: stores workers currently working on the left bank, at most k workers
  • work_in_right: stores workers currently working on the right bank, at most k workers

At any point in time, each of the k workers is in exactly one of these four heaps. Therefore, the total space used by all heaps combined is O(k).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Priority Queue Implementation for Worker Efficiency

Pitfall: Using the original worker indices directly in the priority queues without considering efficiency ordering. This leads to incorrect worker selection when multiple workers are waiting to cross.

Why it happens: The problem states that less efficient workers have priority, but if you use original indices, you might select the wrong worker when multiple are waiting.

Incorrect approach:

# Wrong: Using original indices directly
for i in range(k):
    heappush(wait_in_left, -i)  # This assumes worker 0 is least efficient

Solution: Sort workers by efficiency first, then use the sorted indices:

# Correct: Sort by efficiency first
time.sort(key=lambda x: x[0] + x[2])
# Now index i represents efficiency rank (higher i = less efficient)
for i in range(k):
    heappush(wait_in_left, -i)

2. Mishandling the Termination Condition

Pitfall: Terminating the simulation too early or too late, particularly forgetting to check if workers are still working on the right side.

Why it happens: The simulation should end when the last box reaches the left warehouse, but it's easy to miss edge cases where workers are still picking boxes on the right side.

Incorrect approach:

# Wrong: Only checking if boxes remain
if n == 0:
    return cur

Solution: Check all conditions - no boxes left AND no workers on the right side:

# Correct: Comprehensive termination check
if n == 0 and not wait_in_right and not work_in_right:
    return cur

3. Time Advancement Logic Errors

Pitfall: Not properly advancing time when no workers are waiting to cross the bridge, causing infinite loops or incorrect timing.

Why it happens: When all workers are busy in warehouses, the simulation must jump to the next completion time, but it's easy to miss this case.

Incorrect approach:

# Wrong: Stuck in infinite loop when no one is waiting
while True:
    # Process workers...
    # Missing time advancement when everyone is busy

Solution: Explicitly handle the case when no one can cross:

# Correct: Advance time to next worker completion
if not left_to_go and not right_to_go:
    nxt = inf
    if work_in_left:
        nxt = min(nxt, work_in_left[0][0])
    if work_in_right:
        nxt = min(nxt, work_in_right[0][0])
    cur = nxt
    continue

4. Incorrect Box Count Management

Pitfall: Decrementing the box count at the wrong time - either when a worker starts crossing or when they finish putting the box down.

Why it happens: The box count should decrease when a worker is assigned to transport a box (starts crossing from left), not when they complete delivery.

Incorrect approach:

# Wrong: Decrementing when box is delivered
if wait_in_right:
    i = -heappop(wait_in_right)
    cur += time[i][2]
    n -= 1  # Wrong timing!

Solution: Decrement when a worker is assigned to pick up a box:

# Correct: Decrement when worker goes to pick up a box
if wait_in_left and n > 0:
    i = -heappop(wait_in_left)
    cur += time[i][0]
    n -= 1  # Correct: Box is now assigned to this worker

5. Bridge Priority Rules Violation

Pitfall: Not properly implementing the priority that workers on the right side (carrying boxes) always cross before workers on the left side.

Why it happens: The condition logic can be confusing, especially when determining who can cross.

Incorrect approach:

# Wrong: Checking left side first
if left_to_go:
    # Process left crossing
elif right_to_go:
    # Process right crossing

Solution: Always prioritize right side crossings:

# Correct: Right side has priority
if right_to_go:
    # Process right crossing first
elif left_to_go:
    # Process left crossing only if no one on right
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Recommended Readings

Heap Fundamentals

https assets algo monster cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue is a data structure

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More