# 2532. Time to Cross a Bridge

• Time: $O(n\log n)$
• Space: $O(n)$
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 class Solution { public: int findCrossingTime(int n, int k, vector>& time) { int ans = 0; using P = pair; // (leftToRight + rightToLeft, i) priority_queue

leftBridgeQueue; priority_queue

rightBridgeQueue; // (time to be idle, i) priority_queue, greater<>> leftWorkers; priority_queue, 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; } };

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 class Solution { public int findCrossingTime(int n, int k, int[][] time) { int ans = 0; // (leftToRight + rightToLeft, i) Queue> leftBridgeQueue = createMaxHeap(); Queue> rightBridgeQueue = createMaxHeap(); // (time to be idle, i) Queue> leftWorkers = createMinHeap(); Queue> 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> createMaxHeap() { return new PriorityQueue<>((a, b) -> a.getKey().equals(b.getKey()) ? b.getValue() - a.getValue() : b.getKey() - a.getKey()); } private Queue> createMinHeap() { return new PriorityQueue<>((a, b) -> a.getKey().equals(b.getKey()) ? a.getValue() - b.getValue() : a.getKey() - b.getKey()); } }
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 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