Time to Cross a Bridge — LeetCode 2532 Python Solution
HardArraySimulationHeap (Priority Queue)
- Problem
- #2532
- Pattern
- Heap / Priority Queue
- Reading time
- 8 min
- Source
- leetcode.com
The problem
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].
Example
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.
Python solution
Python
class Solution:
def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:
time.sort(key=lambda x: x[0] + x[2])
cur = 0
wait_in_left, wait_in_right = [], []
work_in_left, work_in_right = [], []
for i in range(k):
heappush(wait_in_left, -i)
while 1:
while work_in_left:
t, i = work_in_left[0]
if t > cur:
break
heappop(work_in_left)
heappush(wait_in_left, -i)
while work_in_right:
t, i = work_in_right[0]
if t > cur:
break
heappop(work_in_right)
heappush(wait_in_right, -i)
left_to_go = n > 0 and wait_in_left
right_to_go = bool(wait_in_right)
if not left_to_go and not right_to_go:
nxt = inf
if work_in_left:
nxt = min(nxt, work_in_left[0][0])
if work_in_right:
nxt = min(nxt, work_in_right[0][0])
cur = nxt
continue
if right_to_go:
i = -heappop(wait_in_right)
cur += time[i][2]
if n == 0 and not wait_in_right and not work_in_right:
return cur
heappush(work_in_left, (cur + time[i][3], i))
else:
i = -heappop(wait_in_left)
cur += time[i][0]
n -= 1
heappush(work_in_right, (cur + time[i][1], i))Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log k) |
| Space | O(k) auxiliary |
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2532. Time to Cross a Bridge is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2532. Time to Cross a Bridge?
- LeetCode 2532. Time to Cross a Bridge is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2532. Time to Cross a Bridge?
- The Python solution on this page runs in O(n \times \log k).
- What is the space complexity of LeetCode 2532. Time to Cross a Bridge?
- The Python solution on this page uses O(k) auxiliary space.
- What topics does LeetCode 2532. Time to Cross a Bridge cover?
- LeetCode 2532. Time to Cross a Bridge is tagged Array, Simulation and Heap (Priority Queue) on LeetCode.