#2532

Time to Cross a Bridge

master · 1630 · lc hard +32 · 44.4% accepted · 123 likes · top 27%

Description

k workers must transport n boxes across a bridge from the right warehouse to the left warehouse. You are given n, k, and a k x 4 array time where time[i] = [righti, picki, lefti, puti] gives the minutes worker i needs to cross right, pick up a box, cross left, and put it down. Only one worker may use the bridge at a time. Worker efficiency is determined by lefti + righti (lower is more efficient; ties broken by higher index). When the bridge is free, workers returning from the right have priority over those heading out from the left. Workers stop being dispatched once enough are already en route for the remaining boxes. Return the minute at which the final box arrives on the left side.

Example 1:

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.

Code

1

2

3

class Solution:
    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:

class Solution:
    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int: