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 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. 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 <= 105
  • 1 <= time[i], totalTrips <= 107

Similar Questions:

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/minimum-time-to-complete-trips/
// 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/minimum-time-to-complete-trips/

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/minimum-time-to-complete-trips/discuss/1802417/

All Problems

All Solutions