In this guide, you will get 2532. Time to Cross a Bridge LeetCode Solution with the best time and space complexity. The solution to Time to Cross a Bridge problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
There are k workers who want to move n boxes from the right (old) warehouse to the left (new) warehouse. You are given the two integers n and k, and a 2D integer array time of size k x 4 where time[i] = [righti, picki, lefti, puti].
The warehouses are separated by a river and connected by a bridge. Initially, all k workers are waiting on the left side of the bridge. To move the boxes, the ith worker can do the following:
Cross the bridge to the right side in righti minutes.
Pick a box from the right warehouse in picki minutes.
Cross the bridge to the left side in lefti minutes.
Put the box into the left warehouse in puti minutes.
The ith worker is less efficient than the jth worker if either condition is met:
lefti + righti > leftj + rightj
lefti + righti == leftj + rightj and i > j
The following rules regulate the movement of the workers through the bridge:
Only one worker can use the bridge at a time.
When the bridge is unused prioritize the least efficient worker (who have picked up the box) on the right side to cross. If not, prioritize the least efficient worker on the left side to cross.
If enough workers have already been dispatched from the left side to pick up all the remaining boxes, no more workers will be sent from the left side.
Return the elapsed minutes at which the last box reaches the left side of the bridge.
Example 1:
Input: n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]
Output: 6
Explanation:
From 0 to 1 minutes: worker 2 crosses the bridge to the right.
From 1 to 2 minutes: worker 2 picks up a box from the right warehouse.
From 2 to 6 minutes: worker 2 crosses the bridge to the left.
From 6 to 7 minutes: worker 2 puts a box at the left warehouse.
The whole process ends after 7 minutes. We return 6 because the problem asks for the instance of time at which the last worker reaches the left side of the bridge.
Input: n = 3, k = 2, time = [[1,5,1,8],[10,10,10,10]]
Output: 37
Explanation:
The last box reaches the left side at 37 seconds. Notice, how we do not put the last boxes down, as that would take more time, and they are already on the left with the workers.
Constraints:
1 <= n, k <= 104
time.length == k
time[i].length == 4
1 <= lefti, picki, righti, puti <= 1000
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
2532. Time to Cross a Bridge LeetCode Solution in C++
class Solution {
public:
int findCrossingTime(int n, int k, vector<vector<int>>& time) {
int ans = 0;
using P = pair<int, int>;
// (leftToRight + rightToLeft, i)
priority_queue<P> leftBridgeQueue;
priority_queue<P> rightBridgeQueue;
// (time to be idle, i)
priority_queue<P, vector<P>, greater<>> leftWorkers;
priority_queue<P, vector<P>, greater<>> rightWorkers;
for (int i = 0; i < k; ++i)
leftBridgeQueue.emplace(
/*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i);
while (n > 0 || !rightBridgeQueue.empty() || !rightWorkers.empty()) {
// Idle left workers get on the left bridge.
while (!leftWorkers.empty() && leftWorkers.top().first <= ans) {
const int i = leftWorkers.top().second;
leftWorkers.pop();
leftBridgeQueue.emplace(
/*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i);
}
// Idle right workers get on the right bridge.
while (!rightWorkers.empty() && rightWorkers.top().first <= ans) {
const int i = rightWorkers.top().second;
rightWorkers.pop();
rightBridgeQueue.emplace(
/*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i);
}
if (!rightBridgeQueue.empty()) {
// If the bridge is free, the worker waiting on the right side of the
// bridge gets to cross the bridge. If more than one worker is waiting
// on the right side, the one with the lowest efficiency crosses first.
const int i = rightBridgeQueue.top().second;
rightBridgeQueue.pop();
ans += /*rightToLeft*/ time[i][2];
leftWorkers.emplace(ans + /*putNew*/ time[i][3], i);
} else if (!leftBridgeQueue.empty() && n > 0) {
// If the bridge is free and no worker is waiting on the right side, and
// at least one box remains at the old warehouse, the worker on the left
// side of the river gets to cross the bridge. If more than one worker
// is waiting on the left side, the one with the lowest efficiency
// crosses first.
const int i = leftBridgeQueue.top().second;
leftBridgeQueue.pop();
ans += /*leftToRight*/ time[i][0];
rightWorkers.emplace(ans + /*pickOld*/ time[i][1], i);
--n;
} else {
// Advance the time of the last crossing worker.
ans = min(
!leftWorkers.empty() && n > 0 ? leftWorkers.top().first : INT_MAX,
!rightWorkers.empty() ? rightWorkers.top().first : INT_MAX);
}
}
return ans;
}
}; /* code provided by PROGIEZ */
2532. Time to Cross a Bridge LeetCode Solution in Java
class Solution {
public int findCrossingTime(int n, int k, int[][] time) {
int ans = 0;
// (leftToRight + rightToLeft, i)
Queue<Pair<Integer, Integer>> leftBridgeQueue = createMaxHeap();
Queue<Pair<Integer, Integer>> rightBridgeQueue = createMaxHeap();
// (time to be idle, i)
Queue<Pair<Integer, Integer>> leftWorkers = createMinHeap();
Queue<Pair<Integer, Integer>> rightWorkers = createMinHeap();
for (int i = 0; i < k; ++i)
leftBridgeQueue.offer(new Pair<>(
/*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i));
while (n > 0 || !rightBridgeQueue.isEmpty() || !rightWorkers.isEmpty()) {
// Idle left workers get on the left bridge.
while (!leftWorkers.isEmpty() && leftWorkers.peek().getKey() <= ans) {
final int i = leftWorkers.poll().getValue();
leftBridgeQueue.offer(new Pair<>(
/*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i));
}
// Idle right workers get on the right bridge.
while (!rightWorkers.isEmpty() && rightWorkers.peek().getKey() <= ans) {
final int i = rightWorkers.poll().getValue();
rightBridgeQueue.offer(new Pair<>(
/*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i));
}
if (!rightBridgeQueue.isEmpty()) {
// If the bridge is free, the worker waiting on the right side of the
// bridge gets to cross the bridge. If more than one worker is waiting
// on the right side, the one with the lowest efficiency crosses first.
final int i = rightBridgeQueue.poll().getValue();
ans += /*rightToLeft*/ time[i][2];
leftWorkers.offer(new Pair<>(ans + /*putNew*/ time[i][3], i));
} else if (!leftBridgeQueue.isEmpty() && n > 0) {
// If the bridge is free and no worker is waiting on the right side, and
// at least one box remains at the old warehouse, the worker on the left
// side of the river gets to cross the bridge. If more than one worker
// is waiting on the left side, the one with the lowest efficiency
// crosses first.
final int i = leftBridgeQueue.poll().getValue();
ans += /*leftToRight*/ time[i][0];
rightWorkers.offer(new Pair<>(ans + /*pickOld*/ time[i][1], i));
--n;
} else {
// Advance the time of the last crossing worker.
ans = Math.min(!leftWorkers.isEmpty() && n > 0 ? leftWorkers.peek().getKey()
: Integer.MAX_VALUE,
!rightWorkers.isEmpty() ? rightWorkers.peek().getKey() : Integer.MAX_VALUE);
}
}
return ans;
}
private Queue<Pair<Integer, Integer>> createMaxHeap() {
return new PriorityQueue<>(Comparator.comparing(Pair<Integer, Integer>::getKey)
.thenComparing(Pair<Integer, Integer>::getValue)
.reversed());
}
private Queue<Pair<Integer, Integer>> createMinHeap() {
return new PriorityQueue<>(Comparator.comparing(Pair<Integer, Integer>::getKey)
.thenComparing(Pair<Integer, Integer>::getValue));
}
} // code provided by PROGIEZ
2532. Time to Cross a Bridge LeetCode Solution in Python
class Solution:
def findCrossingTime(self, n: int, k: int, time: list[list[int]]) -> int:
ans = 0
# (leftToRight + rightToLeft, i)
leftBridgeQueue = [
(-leftToRight - rightToLeft, -i) for i,
(leftToRight, pickOld, rightToLeft, pickNew) in enumerate(time)]
rightBridgeQueue = []
# (time to be idle, i)
leftWorkers = []
rightWorkers = []
heapq.heapify(leftBridgeQueue)
while n > 0 or rightBridgeQueue or rightWorkers:
# Idle left workers get on the left bridge.
while leftWorkers and leftWorkers[0][0] <= ans:
i = heapq.heappop(leftWorkers)[1]
leftWorkers.pop()
heapq.heappush(leftBridgeQueue, (-time[i][0] - time[i][2], -i))
# Idle right workers get on the right bridge.
while rightWorkers and rightWorkers[0][0] <= ans:
i = heapq.heappop(rightWorkers)[1]
heapq.heappush(rightBridgeQueue, (-time[i][0] - time[i][2], -i))
if rightBridgeQueue:
# If the bridge is free, the worker waiting on the right side of the
# bridge gets to cross the bridge. If more than one worker is waiting
# on the right side, the one with the lowest efficiency crosses first.
i = -heapq.heappop(rightBridgeQueue)[1]
ans += time[i][2]
heapq.heappush(leftWorkers, (ans + time[i][3], i))
elif leftBridgeQueue and n > 0:
# If the bridge is free and no worker is waiting on the right side, and
# at least one box remains at the old warehouse, the worker on the left
# side of the river gets to cross the bridge. If more than one worker
# is waiting on the left side, the one with the lowest efficiency
# crosses first.
i = -heapq.heappop(leftBridgeQueue)[1]
ans += time[i][0]
heapq.heappush(rightWorkers, (ans + time[i][1], i))
n -= 1
else:
# Advance the time of the last crossing worker.
ans = min(leftWorkers[0][0] if leftWorkers and n > 0 else math.inf,
rightWorkers[0][0] if rightWorkers else math.inf)
return ans # code by PROGIEZ
