Time to Cross a Bridge

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.

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.

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.

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.

1import java.util.*;2 3class Solution {4    public int findCrossingTime(int n, int k, int[][] time) {5        // Max-heap for waiting workers based on efficiency6        Comparator<Integer> efficiencyComparator = (i, j) -> {7            int efficiency_i = time[i][0] + time[i][2];8            int efficiency_j = time[j][0] + time[j][2];9            if (efficiency_i != efficiency_j) {10                return efficiency_j - efficiency_i; // Higher sum is less efficient11            }12            return j - i; // Higher index is less efficient13        };14 15        PriorityQueue<Integer> waitL = new PriorityQueue<>(efficiencyComparator);16        PriorityQueue<Integer> waitR = new PriorityQueue<>(efficiencyComparator);17 18        // Min-heap for busy workers, ordered by finish time19        PriorityQueue<long[]> workL = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));20        PriorityQueue<long[]> workR = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));21 22        for (int i = 0; i < k; i++) {23            waitL.add(i);24        }25 26        long currentTime = 0;27        int boxesToDispatch = n;28        29        // Loop until all boxes are dispatched and all workers are back on the left.30        // A simpler condition is to just track n boxes delivered.31        while (n > 0) {32            // Move workers who finished their tasks by currentTime33            while (!workL.isEmpty() && workL.peek()[0] <= currentTime) {34                waitL.add((int) workL.poll()[1]);35            }36            while (!workR.isEmpty() && workR.peek()[0] <= currentTime) {37                waitR.add((int) workR.poll()[1]);38            }39 40            // Bridge logic: prioritize right side41            if (!waitR.isEmpty()) {42                int workerIdx = waitR.poll();43                currentTime += time[workerIdx][2]; // Cross to left44                n--;45                if (n == 0) {46                    return (int) currentTime;47                }48                workL.add(new long[]{currentTime + time[workerIdx][3], workerIdx});49            } 50            // Then left side, if there are boxes to pick up51            else if (!waitL.isEmpty() && boxesToDispatch > 0) {52                int workerIdx = waitL.poll();53                currentTime += time[workerIdx][0]; // Cross to right54                workR.add(new long[]{currentTime + time[workerIdx][1], workerIdx});55                boxesToDispatch--;56            } 57            // If bridge is idle, advance time to the next event58            else {59                long nextEventTime = Long.MAX_VALUE;60                if (!workL.isEmpty()) {61                    nextEventTime = Math.min(nextEventTime, workL.peek()[0]);62                }63                if (!workR.isEmpty()) {64                    nextEventTime = Math.min(nextEventTime, workR.peek()[0]);65                }66                currentTime = Math.max(currentTime, nextEventTime);67            }68        }69        70        return (int) currentTime;71    }72}