#2187

Minimum Time to Complete Trips

expert · 1015 · lc medium +32 · verified · 39.6% accepted · 3,080 likes · top 19%

⚑ Classic Binary Search ⚑ Binary Search on Answer Space

Description

You are given an array time where time[i] is the duration in minutes for the i^th bus to complete one trip.

Each bus can run back-to-back trips independently. You are also given an integer totalTrips representing the combined number of trips that all buses must complete.

Return the minimum time needed for all buses together to finish at least totalTrips trips.

Example 1:

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].

The total number of trips completed is 1 + 0 + 0 = 1.

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

The total number of trips completed is 2 + 1 + 0 = 3.

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

The total number of trips completed is 3 + 1 + 1 = 5.

So the minimum time needed for all buses to complete at least 5 trips is 3.

Example 2:

Input: time = [2], totalTrips = 1

Output: 2

Explanation:

There is only one bus, and it will complete its first trip at t = 2.

So the minimum time needed to complete 1 trip is 2.

Code

1

2

3

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int: