Medium

Minimum Time to Complete Trips

LAB

Given trip times for buses, return the minimum time needed to complete totalTrips trips.

EXAMPLES

Example 1

Input
{
  "time": [
    1,
    2,
    3
  ],
  "totalTrips": 5
}

Output
3

FUNCTION SHAPE

time: intArraytotalTrips: int→int

SOLUTION NOTE

Min template. Upper bound: slowest single bus completes all trips.

Reveal reference solution +

pythonREFERENCE

def minimumTime(self, time: List[int], totalTrips: int) -> int:
    def check(t):
        return sum(t // bus for bus in time) >= totalTrips

    left, right = 1, min(time) * totalTrips
    while left < right:
        mid = left + (right - left) // 2
        if check(mid):
            right = mid
        else:
            left = mid + 1
    return left

TimeO(n log(min(time) × totalTrips))

SpaceO(1)

Open on LeetCode ↗