LeetCode 2532: Time to Cross a Bridge
Problem Description
Explanation:
To solve this problem, we can simulate the movement of workers across the bridge. We will maintain two priority queues, one for the workers on the left side of the bridge and one for the workers on the right side. We will iterate through time steps, moving workers according to the given rules.
- Create a class
Workerto represent each worker with their index, time to cross to the right, pick up time, time to cross back, and put down time. - Create two priority queues,
pqRightandpqLeft, to keep track of workers on the right and left sides of the bridge. - Initialize a variable
timeElapsedto keep track of the current time. - Iterate through time steps, moving workers across the bridge based on the rules provided.
- Keep track of the number of boxes picked up and the number of workers who have crossed back to the left side.
- Return the elapsed time when the last box reaches the left side.
Time Complexity: O(nlogn), where n is the number of workers. Space Complexity: O(n).
:
Solutions
import java.util.*;
class Worker {
int index, rightTime, pickTime, leftTime, putTime;
public Worker(int index, int rightTime, int pickTime, int leftTime, int putTime) {
this.index = index;
this.rightTime = rightTime;
this.pickTime = pickTime;
this.leftTime = leftTime;
this.putTime = putTime;
}
}
public int timeToCrossBridge(int n, int k, int[][] time) {
PriorityQueue<Worker> pqRight = new PriorityQueue<>((a, b) -> a.rightTime - b.rightTime);
PriorityQueue<Worker> pqLeft = new PriorityQueue<>((a, b) -> a.leftTime - b.leftTime);
for (int i = 0; i < k; i++) {
Worker worker = new Worker(i, time[i][0], time[i][1], time[i][2], time[i][3]);
pqRight.offer(worker);
}
int timeElapsed = 0, boxesPicked = 0, workersBack = 0;
while (boxesPicked < n) {
if (!pqRight.isEmpty() && (pqLeft.isEmpty() || pqRight.peek().rightTime <= timeElapsed)) {
Worker worker = pqRight.poll();
timeElapsed = Math.max(timeElapsed, worker.rightTime);
timeElapsed += worker.pickTime;
pqLeft.offer(worker);
boxesPicked++;
} else {
Worker worker = pqLeft.poll();
timeElapsed = Math.max(timeElapsed, worker.leftTime);
timeElapsed += worker.putTime;
workersBack++;
if (workersBack >= k) break;
}
}
return timeElapsed;
}Loading editor...