Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2187.html
2187. Minimum Time to Complete Trips (Medium)
You are given an array time
where time[i]
denotes the time taken by the i^{th}
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. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus.
You are also given an integer totalTrips
, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete 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.
Constraints:
1 <= time.length <= 10^{5}
1 <= time[i], totalTrips <= 10^{7}
Similar Questions:
 Minimum Speed to Arrive on Time (Medium)
 Minimized Maximum of Products Distributed to Any Store (Medium)
 Maximum Running Time of N Computers (Hard)
Solution 1. Binary Search
This problem is a classic binary search setup – there is a breakpoint m
where all time < m
are invalid and all time >= m
are valid. Here valid
means that we can finish at least totalTrips
trips given time
.
We can check whether a time
is valid in O(N)
time by traversing A
.

// OJ: https://leetcode.com/problems/minimumtimetocompletetrips/ // Time: O(NlogM) where M is the maximum possible answer // Space: O(1) class Solution { public: long long minimumTime(vector<int>& A, int totalTrips) { long long L = 1, R = LONG_MAX; auto valid = [&](long long time) { // returns true if we can finish `totalTrips` trips given `time` long long sum = 0; for (long long n : A) { sum += time / n; if (sum >= totalTrips) return true; } return false; }; while (L <= R) { long long M = L + (R  L) / 2; if (valid(M)) R = M  1; else L = M + 1; } return L; } };

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) ) ############ # 2187. Minimum Time to Complete Trips # https://leetcode.com/problems/minimumtimetocompletetrips/ class Solution: def minimumTime(self, time: List[int], t: int) > int: n = len(time) def good(x): count = 0 for trip in time: count += x // trip return count >= t left, right = 1, t * max(time) while left < right: mid = left + (right  left) // 2 if good(mid): right = mid else: left = mid + 1 return left

class Solution { public long minimumTime(int[] time, int totalTrips) { int mi = time[0]; for (int v : time) { mi = Math.min(mi, v); } long left = 1, right = (long) mi * totalTrips; while (left < right) { long cnt = 0; long mid = (left + right) >> 1; for (int v : time) { cnt += mid / v; } if (cnt >= totalTrips) { right = mid; } else { left = mid + 1; } } return left; } }

func minimumTime(time []int, totalTrips int) int64 { left, right := 1, 10000000*totalTrips for left < right { mid := (left + right) >> 1 cnt := 0 for _, v := range time { cnt += mid / v } if cnt >= totalTrips { right = mid } else { left = mid + 1 } } return int64(left) }
Discuss
https://leetcode.com/problems/minimumtimetocompletetrips/discuss/1802417/