LeetCode Solutions Blog

Time to Cross a Bridge

Number: 2642

Difficulty: Hard

Paid? No

Companies: LinkedIn

Problem Description

Given n boxes and k workers with their individual times for crossing the bridge (to the right warehouse and back to the left), picking up a box, and putting the box down, simulate the process to determine when the last box is delivered to the left warehouse. Workers are dispatched according to specific priority rules based on their “efficiency” (the sum of left and right crossing times) and an extra rule that prevents sending more workers from the left if there are already enough on the right to handle the remaining boxes.

Key Insights

This is an event simulation problem that must handle workers’ movements between two warehouses.
Use two sets of priority queues (heaps) – one for workers waiting on the left side and one for those waiting on the right – while keeping track of their “ready time.”
The “least efficient” workers (those with a larger sum of left+right times, and in a tie, the ones with a higher index) are prioritized when the bridge is available.
Be careful to only send a worker from the left if there are still boxes that are not “covered” by workers already dispatched to the right.
Time advances to either the next available ready event or when a crossing finishes.

Space and Time Complexity

Time Complexity: O((n + k) * log k) – each event (dispatch, pick, cross, and put) is processed with heap operations. Space Complexity: O(k) – we maintain heaps for up to k workers.

Solution

We simulate the process using two main types of heaps:

Two time-sorted event-queues (min-heaps) for each side (left and right) that hold events when workers become available.
Two “ready” heaps (max-heaps, simulated via negating the efficiency values) that order workers according to the “least efficient” rule among those whose events are ready at the current time.

Each worker’s cycle is simulated in steps:

From the left side: a worker crosses the bridge taking his “right” time; upon arrival, he performs his “pick” action and then is scheduled to wait on the right.
From the right side: when a worker is waiting (i.e. already picked a box), he crosses back with the box (taking his “left” time). This completes the delivery – the crossing finish is recorded as a candidate answer. Afterward, he performs his “put” action and then is scheduled as available on the left side.

A key detail is that we do not dispatch a worker from the left side (even if he is available) when there are already enough workers on the right to handle the remaining boxes (i.e. workersOnRight ≥ remainingBoxes).

We iterate until we have delivered all n boxes. The final answer is the time at which the last worker finishes the crossing from right to left.

Code Solutions

import heapq

# Define a Worker class to hold worker information
class Worker:
    def __init__(self, idx, right, pick, left, put):
        self.idx = idx
        self.right = right
        self.pick = pick
        self.left = left
        self.put = put
        # Efficiency: lower efficiency means a smaller sum. But we need to choose the "least efficient"
        # which is defined as having a larger (left+right) sum, and on tie, larger index.
        self.efficiency = right + left

def timeToCrossBridge(n, k, times):
    # Initialize heaps:
    # left_events and right_events are min-heaps keyed by the time when a worker becomes available.
    # They store entries: (ready_time, worker)
    left_events = []
    right_events = []
    # left_wait and right_wait will be max-heaps (simulate using negative keys)
    # They store entries: ( -efficiency, -idx, ready_time, worker )
    left_wait = []
    right_wait = []
    
    workers = []
    for i, t in enumerate(times):
        worker = Worker(i, t[0], t[1], t[2], t[3])
        workers.append(worker)
        # Initially, all workers are available on the left side at time 0.
        heapq.heappush(left_events, (0, worker))
    
    current_time = 0
    workers_on_right = 0  # Number of workers who are either waiting on the right or en route there.
    delivered = 0
    last_crossing_time = 0
    
    # Simulation loop until all boxes are delivered.
    while delivered < n:
        # Move all left events that are ready into the left_wait heap.
        while left_events and left_events[0][0] <= current_time:
            ready_time, worker = heapq.heappop(left_events)
            heapq.heappush(left_wait, (-worker.efficiency, -worker.idx, ready_time, worker))
        
        # Move all right events that are ready into the right_wait heap.
        while right_events and right_events[0][0] <= current_time:
            ready_time, worker = heapq.heappop(right_events)
            heapq.heappush(right_wait, (-worker.efficiency, -worker.idx, ready_time, worker))
        
        # Priority 1: if any worker is waiting on the right,
        if right_wait:
            # Get the least efficient worker waiting on the right.
            neg_eff, neg_idx, ready_time, worker = heapq.heappop(right_wait)
            # Ensure the current time is at least the worker's ready time.
            current_time = max(current_time, ready_time)
            # Worker crosses from right to left taking his left_time.
            finish_cross = current_time + worker.left
            last_crossing_time = finish_cross  # This crossing delivers a box.
            delivered += 1
            workers_on_right -= 1  # Worker is leaving right side.
            # After crossing, the worker takes put time.
            available_time_left = finish_cross + worker.put
            heapq.heappush(left_events, (available_time_left, worker))
            # Advance current time to when the bridge becomes free.
            current_time = finish_cross
            continue

        # Priority 2: if a worker is available on the left and it is required to dispatch more.
        # Only dispatch if the number of workers on right is less than the remaining boxes.
        if left_wait and workers_on_right < (n - delivered):
            neg_eff, neg_idx, ready_time, worker = heapq.heappop(left_wait)
            current_time = max(current_time, ready_time)
            # Worker crosses from left to right taking his right_time.
            finish_cross = current_time + worker.right
            workers_on_right += 1  # Worker is now on his way to the right.
            # After arriving, worker picks up a box.
            available_time_right = finish_cross + worker.pick
            heapq.heappush(right_events, (available_time_right, worker))
            current_time = finish_cross
            continue

        # If no workers are waiting on either side, jump to the next event time.
        next_times = []
        if left_events and workers_on_right < (n - delivered):
            next_times.append(left_events[0][0])
        if right_events:
            next_times.append(right_events[0][0])
        if not next_times:
            break  # Should not occur if n boxes must be delivered.
        current_time = min(next_times)
    
    return last_crossing_time

# Example usage:
if __name__ == "__main__":
    # Example 1:
    n = 1
    k = 3
    times = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]
    print(timeToCrossBridge(n, k, times))  # Expected output: 6