# Time to Cross a Bridge
**Difficulty:** HARD
[External](https://leetcode.com/problems/time-to-cross-a-bridge)
Canonical: https://scaleengineer.com/dsa/problems/time-to-cross-a-bridge
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin)
---
## Problem
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 `righti` minutes.
* Pick a box from the right warehouse in `picki` minutes.
* Cross the bridge to the left side in `lefti` minutes.
* Put the box into the left warehouse in `puti` minutes.

The `ith` worker is **less efficient** than the j`th` worker if either condition is met:

* `lefti + righti > leftj + rightj`
* `lefti + righti == leftj + rightj` and `i > 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:**

![](https://assets.glich.co/dsa/time-to-cross-a-bridge/image0.png)

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 <= 104`
* `time.length == k`
* `time[i].length == 4`
* `1 <= lefti, picki, righti, puti <= 1000`

# Approaches
## Time-Stepped Simulation
This approach simulates the process by incrementing time one unit at a time. At each time step, it checks the status of all workers and the bridge to see if any state changes occur. This method is straightforward to conceptualize but is computationally expensive.
**Time:** O(T * k * log k), where `T` is the final completion time. `T` can be very large (e.g., `n` times the average cycle time). At each time step, we might need to iterate through and sort the `k` workers, making this approach too slow for the given constraints. · **Space:** O(k), to store the state of each of the `k` workers.
**Pros:** Conceptually simple and easy to understand.
**Cons:** Extremely inefficient for the given constraints. The total simulation time can be very large, leading to a 'Time Limit Exceeded' error.; The complexity is proportional to the total elapsed time, which is not ideal for problems with large time values.
### Explanation
In this method, we maintain the state of each worker, including their location (left/right), their current task (waiting, crossing, picking, putting), and the time they will finish their current task. We also track the state of the bridge (busy/free) and until when it's busy. The simulation proceeds in a loop, incrementing a `currentTime` variable from 0 upwards. In each iteration, we check all workers to see if they have completed their tasks. If the bridge is free, we apply the given priority rules to select a worker from the waiting queues (first from the right, then from the left). The selected worker begins crossing, and their state is updated accordingly. This continues until `n` boxes have reached the left side of the bridge.
### Algorithm
1. Initialize `currentTime = 0`, worker states (location, task, finish time), `boxes_to_move = n`, `boxes_delivered = 0`.
2. Create lists or arrays to represent workers waiting on the left and right sides.
3. Start a loop that continues as long as `boxes_delivered < n`.
4. Inside the loop, for the current `currentTime`:
   a. Iterate through all `k` workers. If a worker's task was scheduled to finish at `currentTime`, update their status (e.g., from 'picking' to 'waiting on right').
   b. Check if the bridge is free (i.e., `currentTime` is greater than or equal to the time the last crossing ends).
   c. If the bridge is free, determine who crosses next:
      i. Check the list of workers waiting on the right. If not empty, find the one with the highest priority (least efficient) and dispatch them.
      ii. If no one from the right crosses, check the list of workers waiting on the left. If not empty and more boxes need to be moved, find the highest priority worker and dispatch them.
      iii. When a worker is dispatched, update their state to 'crossing', calculate their arrival time, and set the bridge's busy-until time.
   d. Increment `currentTime` by 1.
5. The simulation ends when the `n`-th box reaches the left side of the bridge. Return the `currentTime` of that event.

## Discrete Event Simulation with Priority Queues
This optimized approach avoids simulating every single time unit by jumping from one significant "event" to the next. An event is a moment when a worker finishes a task (picking/putting) and becomes available, or when a crossing is completed. This allows the simulation to skip over idle time efficiently, making it suitable for the given constraints.
**Time:** O(n * log k). Each of the `n` boxes requires a round trip. Each part of the trip (crossing, picking, putting) involves a few priority queue operations (add/poll), which take `O(log k)` time. The total number of such operations is proportional to `n`. · **Space:** O(k). The four priority queues, in total, store at most `k` workers at any given time.
**Pros:** Highly efficient as it skips idle time by jumping between events.; Correctly models all the problem's constraints and priority rules.; Scales well with the given input constraints.
**Cons:** More complex to implement compared to a time-stepped simulation.; Requires careful management of state and time using multiple priority queues.
### Explanation
We use four priority queues to manage the workers:
- `waitL` and `waitR`: Max-priority queues for workers waiting on the left and right sides, respectively. The priority is determined by the "least efficient" rule: higher `left_i + right_i` sum, with ties broken by higher index `i`.
- `workL` and `workR`: Min-priority queues for workers busy putting down a box (left) or picking one up (right). They store pairs of `(finishTime, workerIndex)` and are ordered by the earliest `finishTime`.

The simulation revolves around a `currentTime` variable, which represents the time the bridge becomes free after a crossing. Instead of incrementing by one, `currentTime` is advanced based on crossing durations or jumps to the next time a worker becomes free. The simulation loop continues until all `n` boxes have been delivered. This event-driven model is highly efficient because it only processes moments where the system's state changes.

```java
import java.util.*;

class Solution {
    public int findCrossingTime(int n, int k, int[][] time) {
        // Max-heap for waiting workers based on efficiency
        Comparator<Integer> efficiencyComparator = (i, j) -> {
            int efficiency_i = time[i][0] + time[i][2];
            int efficiency_j = time[j][0] + time[j][2];
            if (efficiency_i != efficiency_j) {
                return efficiency_j - efficiency_i; // Higher sum is less efficient
            }
            return j - i; // Higher index is less efficient
        };

        PriorityQueue<Integer> waitL = new PriorityQueue<>(efficiencyComparator);
        PriorityQueue<Integer> waitR = new PriorityQueue<>(efficiencyComparator);

        // Min-heap for busy workers, ordered by finish time
        PriorityQueue<long[]> workL = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        PriorityQueue<long[]> workR = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));

        for (int i = 0; i < k; i++) {
            waitL.add(i);
        }

        long currentTime = 0;
        int boxesToDispatch = n;
        
        // Loop until all boxes are dispatched and all workers are back on the left.
        // A simpler condition is to just track n boxes delivered.
        while (n > 0) {
            // Move workers who finished their tasks by currentTime
            while (!workL.isEmpty() && workL.peek()[0] <= currentTime) {
                waitL.add((int) workL.poll()[1]);
            }
            while (!workR.isEmpty() && workR.peek()[0] <= currentTime) {
                waitR.add((int) workR.poll()[1]);
            }

            // Bridge logic: prioritize right side
            if (!waitR.isEmpty()) {
                int workerIdx = waitR.poll();
                currentTime += time[workerIdx][2]; // Cross to left
                n--;
                if (n == 0) {
                    return (int) currentTime;
                }
                workL.add(new long[]{currentTime + time[workerIdx][3], workerIdx});
            } 
            // Then left side, if there are boxes to pick up
            else if (!waitL.isEmpty() && boxesToDispatch > 0) {
                int workerIdx = waitL.poll();
                currentTime += time[workerIdx][0]; // Cross to right
                workR.add(new long[]{currentTime + time[workerIdx][1], workerIdx});
                boxesToDispatch--;
            } 
            // If bridge is idle, advance time to the next event
            else {
                long nextEventTime = Long.MAX_VALUE;
                if (!workL.isEmpty()) {
                    nextEventTime = Math.min(nextEventTime, workL.peek()[0]);
                }
                if (!workR.isEmpty()) {
                    nextEventTime = Math.min(nextEventTime, workR.peek()[0]);
                }
                currentTime = Math.max(currentTime, nextEventTime);
            }
        }
        
        return (int) currentTime;
    }
}
```
### Algorithm
1. **Initialization**:
   - `currentTime = 0`.
   - Four priority queues: `waitL`, `waitR` (max-heaps for waiting workers, prioritized by inefficiency), `workL`, `workR` (min-heaps for busy workers, prioritized by finish time).
   - Add all `k` workers to `waitL`.
   - `boxesToDispatch = n` (boxes to be picked up from the right).

2. **Simulation Loop**: Continue as long as there are boxes to be moved or workers on the right side.

3. **Advance Time and Update States**:
   - At the start of each loop, move any workers from `workL` and `workR` whose tasks are finished (i.e., `finishTime <= currentTime`) to their respective waiting queues (`waitL` or `waitR`).

4. **Bridge Logic**:
   - **Priority Right**: If `waitR` is not empty, poll the highest-priority worker. Update `currentTime` by adding their left-crossing time. This new `currentTime` is when they reach the left bank. If this is the last box, return `currentTime`. Otherwise, add the worker to `workL` with their 'put down' finish time.
   - **Priority Left**: If `waitR` is empty but `waitL` is not, and there are still boxes to dispatch (`boxesToDispatch > 0`), poll the highest-priority worker from `waitL`. Update `currentTime` by adding their right-crossing time. Add the worker to `workR` with their 'pick up' finish time and decrement `boxesToDispatch`.
   - **Idle Bridge**: If no worker can cross (e.g., no one is waiting, or all dispatchable workers are on the left but no more boxes are needed), the system is idle. Advance `currentTime` to the earliest finish time of any worker in `workL` or `workR`.

5. **Termination**: The loop terminates when the `n`-th box reaches the left side of the bridge, and that `currentTime` is returned.

# Solutions
### Java

```java
class Solution {
public
  int findCrossingTime(int n, int k, int[][] time) {
    int[][] t = new int[k][5];
    for (int i = 0; i < k; ++i) {
      int[] x = time[i];
      t[i] = new int[]{x[0], x[1], x[2], x[3], i};
    }
    Arrays.sort(
        t, (a, b)->{
          int x = a[0] + a[2], y = b[0] + b[2];
          return x == y ? a[4] - b[4] : x - y;
        });
    int cur = 0;
    PriorityQueue<Integer> waitInLeft = new PriorityQueue<>((a, b)->b - a);
    PriorityQueue<Integer> waitInRight = new PriorityQueue<>((a, b)->b - a);
    PriorityQueue<int[]> workInLeft = new PriorityQueue<>((a, b)->a[0] - b[0]);
    PriorityQueue<int[]> workInRight = new PriorityQueue<>((a, b)->a[0] - b[0]);
    for (int i = 0; i < k; ++i) {
      waitInLeft.offer(i);
    }
    while (true) {
      while (!workInLeft.isEmpty()) {
        int[] p = workInLeft.peek();
        if (p[0] > cur) {
          break;
        }
        waitInLeft.offer(workInLeft.poll()[1]);
      }
      while (!workInRight.isEmpty()) {
        int[] p = workInRight.peek();
        if (p[0] > cur) {
          break;
        }
        waitInRight.offer(workInRight.poll()[1]);
      }
      boolean leftToGo = n > 0 && !waitInLeft.isEmpty();
      boolean rightToGo = !waitInRight.isEmpty();
      if (!leftToGo && !rightToGo) {
        int nxt = 1 << 30;
        if (!workInLeft.isEmpty()) {
          nxt = Math.min(nxt, workInLeft.peek()[0]);
        }
        if (!workInRight.isEmpty()) {
          nxt = Math.min(nxt, workInRight.peek()[0]);
        }
        cur = nxt;
        continue;
      }
      if (rightToGo) {
        int i = waitInRight.poll();
        cur += t[i][2];
        if (n == 0 && waitInRight.isEmpty() && workInRight.isEmpty()) {
          return cur;
        }
        workInLeft.offer(new int[]{cur + t[i][3], i});
      } else {
        int i = waitInLeft.poll();
        cur += t[i][0];
        --n;
        workInRight.offer(new int[]{cur + t[i][1], i});
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findCrossingTime(int n, int k, vector<vector<int>> &time) {
    using pii = pair<int, int>;
    for (int i = 0; i < k; ++i) {
      time[i].push_back(i);
    }
    sort(time.begin(), time.end(), [](auto &a, auto &b) {
      int x = a[0] + a[2], y = b[0] + b[2];
      return x == y ? a[4] < b[4] : x < y;
    });
    int cur = 0;
    priority_queue<int> waitInLeft, waitInRight;
    priority_queue<pii, vector<pii>, greater<pii>> workInLeft, workInRight;
    for (int i = 0; i < k; ++i) {
      waitInLeft.push(i);
    }
    while (true) {
      while (!workInLeft.empty()) {
        auto [t, i] = workInLeft.top();
        if (t > cur) {
          break;
        }
        workInLeft.pop();
        waitInLeft.push(i);
      }
      while (!workInRight.empty()) {
        auto [t, i] = workInRight.top();
        if (t > cur) {
          break;
        }
        workInRight.pop();
        waitInRight.push(i);
      }
      bool leftToGo = n > 0 && !waitInLeft.empty();
      bool rightToGo = !waitInRight.empty();
      if (!leftToGo && !rightToGo) {
        int nxt = 1 << 30;
        if (!workInLeft.empty()) {
          nxt = min(nxt, workInLeft.top().first);
        }
        if (!workInRight.empty()) {
          nxt = min(nxt, workInRight.top().first);
        }
        cur = nxt;
        continue;
      }
      if (rightToGo) {
        int i = waitInRight.top();
        waitInRight.pop();
        cur += time[i][2];
        if (n == 0 && waitInRight.empty() && workInRight.empty()) {
          return cur;
        }
        workInLeft.push({cur + time[i][3], i});
      } else {
        int i = waitInLeft.top();
        waitInLeft.pop();
        cur += time[i][0];
        --n;
        workInRight.push({cur + time[i][1], i});
      }
    }
  }
};

```

### Python

```python
class Solution:
    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int: time . sort(key=lambda x: x[0] + x[2]) cur = 0 wait_in_left, wait_in_right = [], [] work_in_left, work_in_right = [], [] for i in range(k): heappush(wait_in_left, - i) while 1: while work_in_left: t, i = work_in_left[0] if t > cur: break heappop(work_in_left) heappush(wait_in_left, - i) while work_in_right: t, i = work_in_right[0] if t > cur: break heappop(work_in_right) heappush(wait_in_right, - i) left_to_go = n > 0 and wait_in_left right_to_go = bool(wait_in_right) 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 if right_to_go: i = - heappop(wait_in_right) cur += time[i][2] if n == 0 and not wait_in_right and not work_in_right: return cur heappush(work_in_left, (cur + time[i][3], i)) else: i = - heappop(wait_in_left) cur += time[i][0] n -= 1 heappush(work_in_right, (cur + time[i][1], i))

```