Minimum Time to Complete Trips — LeetCode 2187 Python Solution

The problem

You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip. Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip.

Example

Input

time = [1,2,3], totalTrips = 5

Output

3

Explanation

- At time t = 1, the number of trips completed by each bus are [1,0,0].

Python solution

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        mx = min(time) * totalTrips
        return bisect_left(
            range(mx), totalTrips, key=lambda x: sum(x // v for v in time)
        )

Complexity

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 2187. Minimum Time to Complete Trips is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems