2532. Time to Cross a Bridge

HardArraySimulationHeap (Priority Queue)

Problem Description

In this problem, we have a scenario where k workers are tasked with moving n boxes from an old warehouse to a new warehouse across a river. The time array tells us how many minutes each worker takes to perform four actions: crossing the bridge from the new warehouse to the old warehouse (leftToRight), picking a box from the old warehouse (pickOld), crossing back to the new warehouse (rightToLeft), and putting the box in the new warehouse (putNew). We need to calculate the moment in time when the last worker reaches the left bank of the river (new warehouse) after all n boxes have been moved.

Workers cannot cross the bridge simultaneously; if a worker arrives at the bridge while another is crossing, they must wait. The bridge allows for a prioritization where the least efficient worker (based on crossing times) on the waiting side will cross next, with ties broken by worker index. The goal is to determine the time when the final box is put into the new warehouse and all workers are back on the left bank.

Intuition

To solve this problem, a clear strategy is needed to manage the efficient movements of workers across the bridge. First, we must acknowledge that the total efficiency of a worker is based on the sum of their crossing times (both to and from the old warehouse). Second, we recognize that waiting times at both ends of the bridge are crucial to overall efficiency.

The solution works in the following steps:

Sort workers based on their crossing efficiency.
Use two heaps (queues) to manage workers waiting at the left bank and the right bank.
Use two lists to keep track of workers currently crossing to or from each side.
Track the current time and update it as workers move and perform tasks.
Choose workers to cross the bridge based on their efficiency and the current situation.
Update the time when all boxes have been moved, and no worker is crossing from the right bank (old warehouse).

The code snippet handles the simulation of these actions, carefully advancing time, and managing the queues/lists of workers before, during, and after crossing the bridge until the task is completed. This captures the state of each worker and the number of boxes left as the simulation progresses.

By breaking down worker movement into discrete steps and managing them in priority queues, the code can efficiently track the current time needed to move all the boxes while adhering to the problem's constraints.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The solution approach is a simulation that keeps track of the time as workers move boxes across the river. Here's a breakdown of how the implementation manages this complex process:

Sorting Workers by Efficiency: Before beginning the simulation, it sorts the workers based on their total crossing time, which is the sum of leftToRight and rightToLeft times. If a tie occurs, the worker with the smaller index is considered more efficient. This is depicted in the code by the statement time.sort(key=lambda x: x[0] + x[2]).
Priority Queues (Heaps): The code utilizes priority queues (heapq in Python) for managing the workers waiting at both ends of the bridge. Workers at the left bank are placed in a heap wait_in_left, and workers at the right bank in wait_in_right. These heaps prioritize workers with lower efficiency, so when a worker can cross the bridge, the least efficient worker is chosen.
Tracking Workers Crossing: Two additional lists, work_in_left and work_in_right, keep track of workers currently in the process of crossing or about to cross the bridge from the respective sides. These lists store tuples of time when the worker will complete the action and the worker's index.
Time Simulation: The variable cur represents the current time within the simulation. It is advanced to the next significant event, which might be a worker reaching the other side of the bridge, or starting to cross when the bridge is free.
Worker Movement Logic: The core of the solution involves deciding when a worker can move. If the bridge is free, a choice is made between a worker on the right waiting to come back or a worker on the left waiting to pick a box and cross over. If workers are on the right side, they have priority; otherwise, a worker on the left side is allowed to cross. Additionally, workers can only move boxes if there are boxes remaining (n > 0).
Event Management: It continuously checks work_in_left and work_in_right to see if any workers have finished crossing and updates wait_in_left or wait_in_right accordingly. If no workers are waiting and the bridge is free, it determines when the next event occurs by finding the minimum time a worker will finish their task.
End Condition: The simulation continues until there are no more boxes to move (n == 0) and no worker is waiting to cross the bridge from the right side. When this condition is met, the current time cur is the time when the last worker reaches the left bank, which is returned as the final solution to the problem.

By carefully queuing and dequeuing workers and adjusting the time as these events occur, the code efficiently simulates the constrained crossing process and computes the final time required to move all boxes across the bridge to the new warehouse.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we have k = 2 workers and n = 3 boxes to move. Time for each worker is given in the time array as follows:

Worker 0: [1, 2, 3, 4] (i.e., leftToRight = 1, pickOld = 2, rightToLeft = 3, putNew = 4)
Worker 1: [2, 2, 2, 2] (i.e., leftToRight = 2, pickOld = 2, rightToLeft = 2, putNew = 2)

Step 1: Sorting Workers by Efficiency

The total crossing times are 4 for Worker 0 and 4 for Worker 1. Since they are tied in efficiency, we use their index to sort them, resulting in the same order they are given.

Step 2: Priority Queues (Heaps)

We initialize two heaps: wait_in_left initially contains both workers 0 and 1, while wait_in_right is empty since no one has crossed yet.

Step 3: Tracking Workers Crossing

Both work_in_left and work_in_right are initially empty.

Step 4: Time Simulation

The variable cur starts at 0.

Step 5: Worker Movement Logic

Worker 0 starts by crossing the bridge (taking 1 minute), then Worker 1 crosses as well. Once Worker 0 reaches the right bank, they pick a box (taking 2 minutes) and cross back (taking 3 minutes), and put the box in the new warehouse (taking 4 minutes).

Step 6: Event Management

As Worker 0 is moving, Worker 1 also performs their actions after crossing the bridge: picking a box and crossing back. Since Worker 1 has the same crossing time, they wait until Worker 0 has fully crossed before starting their journey back.

Step 7: End Condition

The process is repeated until all n = 3 boxes are moved. Worker 1 might be the last to cross back, as after moving one box, and we assume Worker 0 is quicker at the other tasks. Finally, cur is updated to the moment when the last worker arrives at the left bank, marking the end of the procedure.

In this scenario, cur would be 0 initially, and then it would track the sequence of actions across time:

At cur = 1, Worker 0 has crossed to the right bank.
At cur = 3, Worker 0 has picked a box. Meanwhile, Worker 1 has crossed to the right bank at cur = 2.
Worker 0 starts to cross back at cur = 3 and arrives at cur = 6, and Worker 1 starts picking a box at the same time.
Worker 0 puts the first box at cur = 10, while Worker 1 starts crossing back with their first box at cur = 5.
Repeat these steps until no boxes are left and both workers have crossed back to the left bank for the last time.

We assume perfect efficiency and no waiting time between tasks for simplicity, but in a real scenario, times would overlap and require careful tracking, which the algorithm provides. The final cur would then be the solution to the problem, the moment when the last worker reaches the left bank after all boxes are moved.

Solution Implementation

1from typing import List
2from heapq import heappush, heappop
3
4class Solution:
5    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:
6        # Sort the list of times based on time to cross from left to right and back
7        time.sort(key=lambda x: x[0] + x[2])
8      
9        current_time = 0  # Initialize the current time
10        wait_left, wait_right = [], []  # Queues for people waiting to cross from the left and right
11        work_left, work_right = [], []  # Heaps for people currently crossing from left and right
12      
13        # Initialize the waiting queue on the left with k people
14        for i in range(k):
15            heappush(wait_left, -i)
16      
17        # Loop until there are no more people waiting or working in either direction
18        while True:
19            # Clear people from the left working heap if they have finished crossing
20            while work_left:
21                crossing_time, person_idx = work_left[0]
22                if crossing_time > current_time:
23                    break
24                heappop(work_left)
25                heappush(wait_left, -person_idx)
26
27            # Clear people from the right working heap if they have finished crossing
28            while work_right:
29                crossing_time, person_idx = work_right[0]
30                if crossing_time > current_time:
31                    break
32                heappop(work_right)
33                heappush(wait_right, -person_idx)
34          
35            # Decide if there is anybody to cross from left or right
36            left_to_cross = n > 0 and wait_left
37            right_to_cross = bool(wait_right)
38
39            # If nobody left to cross and no work in progress, find the next time event
40            if not left_to_cross and not right_to_cross:
41                next_event = float('inf')
42                if work_left:
43                    next_event = min(next_event, work_left[0][0])
44                if work_right:
45                    next_event = min(next_event, work_right[0][0])
46                current_time = next_event
47                continue
48          
49            # If there is someone on the right, cross them
50            if right_to_cross:
51                person_idx = -heappop(wait_right)
52                current_time += time[person_idx][2]  # Add time to cross from right to left
53                if n == 0 and not wait_right and not work_right:
54                    return current_time
55                heappush(work_left, (current_time + time[person_idx][3], person_idx))
56            else:
57                # Otherwise, cross person from the left
58                person_idx = -heappop(wait_left)
59                current_time += time[person_idx][0]  # Add time to cross from left to right
60                n -= 1
61                heappush(work_right, (current_time + time[person_idx][1], person_idx))
62
63        # This return statement is unreachable, but formally required
64        return current_time
65

1import java.util.Arrays;
2import java.util.PriorityQueue;
3
4class Solution {
5    public int findCrossingTime(int totalPerson, int totalPasses, int[][] times) {
6        // Standardize the times array with additional index to maintain original order
7        int[][] standardizedTimes = new int[totalPasses][5];
8        for (int i = 0; i < totalPasses; ++i) {
9            int[] currentPass = times[i];
10            standardizedTimes[i] = new int[]{currentPass[0], currentPass[1], currentPass[2], currentPass[3], i};
11        }
12
13        // Sort the standardized times based on the sum of arriveLeft + crossToLeft
14        // and if they are the same, sort by the original index
15        Arrays.sort(standardizedTimes, (a, b) -> {
16            int timeA = a[0] + a[2];
17            int timeB = b[0] + b[2];
18            return timeA == timeB ? a[4] - b[4] : timeA - timeB;
19        });
20      
21        // Initialize the current time
22        int currentTime = 0;
23      
24        // Priority queues for keeping track of the waiting times
25        PriorityQueue<Integer> waitingLeft = new PriorityQueue<>((a, b) -> b - a);
26        PriorityQueue<Integer> waitingRight = new PriorityQueue<>((a, b) -> b - a);
27      
28        // Priority queues for keeping track of the work times (i.e. crossing times)
29        PriorityQueue<int[]> workingLeft = new PriorityQueue<>((a, b) -> a[0] - b[0]);
30        PriorityQueue<int[]> workingRight = new PriorityQueue<>((a, b) -> a[0] - b[0]);
31      
32        // Initially, fill the waitingLeft queue with all persons
33        for (int i = 0; i < totalPasses; ++i) {
34            waitingLeft.offer(i);
35        }
36      
37        // Process until there are no persons left to cross or waiting for crossing
38        while (true) {
39            // Move from workingLeft to waitingLeft if the working time is past
40            while (!workingLeft.isEmpty() && workingLeft.peek()[0] <= currentTime) {
41                waitingLeft.offer(workingLeft.poll()[1]);
42            }
43          
44            // Move from workingRight to waitingRight if the working time is past
45            while (!workingRight.isEmpty() && workingRight.peek()[0] <= currentTime) {
46                waitingRight.offer(workingRight.poll()[1]);
47            }
48          
49            // Determine if there are persons to go from left and right
50            boolean leftToGo = totalPerson > 0 && !waitingLeft.isEmpty();
51            boolean rightToGo = !waitingRight.isEmpty();
52          
53            // If no one is left to go from either side, find the next event time
54            if (!leftToGo && !rightToGo) {
55                int nextEventTime = Integer.MAX_VALUE;
56                if (!workingLeft.isEmpty()) {
57                    nextEventTime = Math.min(nextEventTime, workingLeft.peek()[0]);
58                }
59                if (!workingRight.isEmpty()) {
60                    nextEventTime = Math.min(nextEventTime, workingRight.peek()[0]);
61                }
62                currentTime = nextEventTime;
63                continue;
64            }
65          
66            // Move persons from right to left
67            if (rightToGo) {
68                int index = waitingRight.poll();
69                currentTime += standardizedTimes[index][2];
70                // Check for completion condition when no one is left to cross
71                if (totalPerson == 0 && waitingRight.isEmpty() && workingRight.isEmpty()) {
72                    return currentTime;
73                }
74                workingLeft.offer(new int[]{currentTime + standardizedTimes[index][3], index});
75            } else {
76                // Move persons from left to right
77                int index = waitingLeft.poll();
78                currentTime += standardizedTimes[index][0];
79                totalPerson--;
80                workingRight.offer(new int[]{currentTime + standardizedTimes[index][1], index});
81            }
82        }
83    }
84}
85

1#include <vector>
2#include <queue>
3#include <algorithm>
4#include <utility>
5
6class Solution {
7public:
8    // Find the time needed for all people to cross the bridge.
9    int findCrossingTime(int numPeople, int numGroups, std::vector<std::vector<int>>& groupTimes) {
10        // Using 'pair' as a shorthand for convenience
11        using Pair = std::pair<int, int>;
12      
13        // Adding group index to each group's time vector
14        for (int i = 0; i < numGroups; ++i) {
15            groupTimes[i].push_back(i);
16        }
17      
18        // Sort the groups based on the total time (departure + arrival) and if equal, by the group index
19        sort(groupTimes.begin(), groupTimes.end(), [](const auto& a, const auto& b) {
20            int totalTimeA = a[0] + a[2];
21            int totalTimeB = b[0] + b[2];
22            return totalTimeA == totalTimeB ? a[4] < b[4] : totalTimeA < totalTimeB;
23        });
24      
25        int currentTime = 0;
26        std::priority_queue<int> waitingOnLeft, waitingOnRight;
27        std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> workingOnLeft, workingOnRight;
28      
29        // Add all groups to the waiting queue on the left side
30        for (int i = 0; i < numGroups; ++i) {
31            waitingOnLeft.push(i);
32        }
33      
34        while (true) {
35            // Move groups from workingOnLeft to waitingOnLeft once their work is done
36            while (!workingOnLeft.empty()) {
37                auto [finishTime, groupIndex] = workingOnLeft.top();
38                if (finishTime > currentTime) {
39                    break;
40                }
41                workingOnLeft.pop();
42                waitingOnLeft.push(groupIndex);
43            }
44          
45            // Move groups from workingOnRight to waitingOnRight once their work is done
46            while (!workingOnRight.empty()) {
47                auto [finishTime, groupIndex] = workingOnRight.top();
48                if (finishTime > currentTime) {
49                    break;
50                }
51                workingOnRight.pop();
52                waitingOnRight.push(groupIndex);
53            }
54          
55            // Determine if there are groups ready to cross from both sides
56            bool canCrossFromLeft = numPeople > 0 && !waitingOnLeft.empty();
57            bool canCrossFromRight = !waitingOnRight.empty();
58          
59            // When no one is left to cross
60            if (!canCrossFromLeft && !canCrossFromRight) {
61                int nextEventTime = INT_MAX;
62                if (!workingOnLeft.empty()) {
63                    nextEventTime = std::min(nextEventTime, workingOnLeft.top().first);
64                }
65                if (!workingOnRight.empty()) {
66                    nextEventTime = std::min(nextEventTime, workingOnRight.top().first);
67                }
68                currentTime = nextEventTime;
69                continue;
70            }
71          
72            // Cross from right to left
73            if (canCrossFromRight) {
74                int groupIndex = waitingOnRight.top();
75                waitingOnRight.pop();
76                currentTime += groupTimes[groupIndex][2];
77                // If it's the last person crossing to the left side, return the time
78                if (numPeople == 0 && waitingOnRight.empty() && workingOnRight.empty()) {
79                    return currentTime;
80                }
81                // Add the group to the working queue on the left side
82                workingOnLeft.push({currentTime + groupTimes[groupIndex][3], groupIndex});
83            } else {
84                // Cross from left to right
85                int groupIndex = waitingOnLeft.top();
86                waitingOnLeft.pop();
87                currentTime += groupTimes[groupIndex][0];
88                --numPeople;
89                // Add the group to the working queue on the right side
90                workingOnRight.push({currentTime + groupTimes[groupIndex][1], groupIndex});
91            }
92        }
93    }
94};
95

1function findCrossingTime(numPeople: number, numGroups: number, groupTimes: number[][]): number {
2    // Sort the groups based on the total time (departure + arrival) and, if equal, by the group index
3    groupTimes.forEach((group, index) => group.push(index));
4    groupTimes.sort((a, b) => {
5        const totalTimeA = a[0] + a[2];
6        const totalTimeB = b[0] + b[2];
7        return totalTimeA === totalTimeB ? a[4] - b[4] : totalTimeA - totalTimeB;
8    });
9
10    let currentTime = 0;
11    const waitingOnLeft: number[] = [];
12    const waitingOnRight: number[] = [];
13    const workingOnLeft: Array<[number, number]> = [];
14    const workingOnRight: Array<[number, number]> = [];
15
16    // Add all groups to the waiting queue on the left side
17    for (let i = 0; i < numGroups; ++i) {
18        waitingOnLeft.push(i);
19    }
20
21    while (true) {
22        // Move groups from workingOnLeft to waitingOnLeft once their work is done
23        while (workingOnLeft.length > 0 && workingOnLeft[0][0] <= currentTime) {
24            const [_, groupIndex] = workingOnLeft.shift()!;
25            waitingOnLeft.push(groupIndex);
26        }
27
28        // Move groups from workingOnRight to waitingOnRight once their work is done
29        while (workingOnRight.length > 0 && workingOnRight[0][0] <= currentTime) {
30            const [_, groupIndex] = workingOnRight.shift()!;
31            waitingOnRight.push(groupIndex);
32        }
33
34        // Determine if there are groups ready to cross from both sides
35        const canCrossFromLeft = numPeople > 0 && waitingOnLeft.length > 0;
36        const canCrossFromRight = waitingOnRight.length > 0;
37
38        // When no one is left to cross
39        if (!canCrossFromLeft && !canCrossFromRight) {
40            const nextEventTime = Math.min(
41                ...workingOnLeft.map(([time, _]) => time),
42                ...workingOnRight.map(([time, _]) => time),
43                Infinity
44            );
45            currentTime = nextEventTime;
46            continue;
47        }
48
49        // Sort the working groups by the finished time to get the correct order
50        workingOnLeft.sort((a, b) => a[0] - b[0]);
51        workingOnRight.sort((a, b) => a[0] - b[0]);
52
53        // Cross from right to left
54        if (canCrossFromRight) {
55            const groupIndex = waitingOnRight.shift()!;
56            currentTime += groupTimes[groupIndex][2];
57          
58            if (numPeople === 0 && waitingOnRight.length === 0 && workingOnRight.length === 0) {
59                return currentTime;
60            }
61          
62            // Add the group to the working queue on the left side
63            workingOnLeft.push([currentTime + groupTimes[groupIndex][3], groupIndex]);
64        } else if (canCrossFromLeft) {
65            // Cross from left to right
66            const groupIndex = waitingOnLeft.shift()!;
67            currentTime += groupTimes[groupIndex][0];
68            numPeople--;
69          
70            // Add the group to the working queue on the right side
71            workingOnRight.push([currentTime + groupTimes[groupIndex][1], groupIndex]);
72        }
73
74        // Sort the waiting groups by their group index before proceeding to the next iteration
75        waitingOnLeft.sort((a, b) => a - b);
76        waitingOnRight.sort((a, b) => a - b);
77    }
78}
79

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be attributed to the following operations:

Sorting the time list, which takes O(k log k), where k is the length of the time list.
Heap operations on work_in_left and work_in_right. Since these operations occur at most once for each person, and there are O(k) persons, each heap operation takes O(log k). Hence, the total for all heap push and pop operations across the entire input set is O(k log k).
The while loop runs until all people have crossed, which is also at most k times. Within the loop, there are constant heap operations, so this contributes another O(k log k).

Combining these, we have O(k log k) for the sort, plus O(k log k) for the loop, thus the time complexity is O(k log k).

Space Complexity

The space complexity of the code can be analyzed based on the data structures used:

The lists wait_in_left, wait_in_right, work_in_left, and work_in_right can all potentially store up to k elements since they are directly related to the number of people waiting or already on the bridge. This gives us O(k) space.
The time list is sorted in-place, so it does not require additional space beyond the input.

Therefore, the space complexity of the code is O(k).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know