LeetCode Solutions Blog

Time to Cross a Bridge

Difficulty: Hard

Problem Description

There are k workers who want to move n boxes from the right (old) warehouse to the left (new) warehouse. You are given two integers n and k, and a 2D integer array time of size k x 4 where time[i] = [right_i, pick_i, left_i, put_i]. The elapsed minutes at which the last box reaches the left side of the bridge needs to be returned.

Key Insights

Each worker's efficiency is defined by the sum of their crossing times (right + left).
Workers must cross the bridge one at a time, with the least efficient worker prioritized.
The process involves multiple steps: crossing to the right, picking a box, crossing back to the left, and putting down the box.
If enough workers are dispatched to pick up all remaining boxes, no more workers will be sent from the left side.

Space and Time Complexity

Time Complexity: O(n log k) - Each box requires a series of operations involving a priority queue for worker selection.

Space Complexity: O(k) - We maintain a priority queue to track workers' states.

Solution

The solution utilizes a priority queue (min-heap) to manage the workers based on their efficiency. We simulate the process where workers are sent to the right side to pick boxes and then return to the left side to drop them off. The steps are tracked using timestamps, ensuring that we account for the time each worker spends during their operations. By prioritizing the least efficient worker for crossing, we can ensure optimal time management.

Code Solutions

import heapq

def time_to_cross_bridge(n, k, time):
    workers = []
    for i in range(k):
        right, pick, left, put = time[i]
        efficiency = left + right
        workers.append((efficiency, i, right, pick, left, put))
    
    # Min-heap based on efficiency and worker index
    heapq.heapify(workers)
    
    current_time = 0
    boxes_on_left = 0
    right_workers = []  # To store workers who are currently on the right side
    left_workers = []   # To store workers who are currently on the left side
    
    while boxes_on_left < n:
        if right_workers:
            # Process the least efficient worker on the right
            efficiency, idx, right, pick, left, put = heapq.heappop(right_workers)
            current_time += left  # Cross back to the left
            boxes_on_left += 1
            current_time += put    # Put down the box
        
        # Send the next worker from the left if there are boxes left
        if boxes_on_left < n:
            if workers:
                efficiency, idx, right, pick, left, put = heapq.heappop(workers)
                current_time += right  # Cross to the right
                current_time += pick    # Pick up a box
                heapq.heappush(right_workers, (efficiency, idx, right, pick, left, put))
    
    return current_time - 1  # Last box reaches just before the put down time

# Example usage
print(time_to_cross_bridge(1, 3, [[1,1,2,1],[1,1,3,1],[1,1,4,1]]))  # Output: 6