2532. Time to Cross a Bridge
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.
What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
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
leftToRightandrightToLefttimes. If a tie occurs, the worker with the smaller index is considered more efficient. This is depicted in the code by the statementtime.sort(key=lambda x: x[0] + x[2]). -
Priority Queues (Heaps): The code utilizes priority queues (
heapqin Python) for managing the workers waiting at both ends of the bridge. Workers at the left bank are placed in a heapwait_in_left, and workers at the right bank inwait_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_leftandwork_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
currepresents 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_leftandwork_in_rightto see if any workers have finished crossing and updateswait_in_leftorwait_in_rightaccordingly. 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 timecuris 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.
Which of the following shows the order of node visit in a Breadth-first Search?
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 atcur = 2. - Worker 0 starts to cross back at
cur = 3and arrives atcur = 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 atcur = 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
651import 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}
851#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};
951function 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}
79The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be attributed to the following operations:
- Sorting the
timelist, which takesO(k log k), wherekis the length of the time list. - Heap operations on
work_in_leftandwork_in_right. Since these operations occur at most once for each person, and there areO(k)persons, each heap operation takesO(log k). Hence, the total for all heap push and pop operations across the entire input set isO(k log k). - The while loop runs until all people have crossed, which is also at most
ktimes. Within the loop, there are constant heap operations, so this contributes anotherO(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, andwork_in_rightcan all potentially store up tokelements since they are directly related to the number of people waiting or already on the bridge. This gives usO(k)space. - The
timelist 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.
Which technique can we use to find the middle of a linked list?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.