Minimum Time to Complete Trips
Problem
Each bus i takes time[i] units per trip and they run in parallel. Given totalTrips, return the minimum time required for the buses combined to make at least totalTrips trips.
time = [1, 2, 3], totalTrips = 53def minimum_time(time, total_trips):
lo, hi = 1, min(time) * total_trips
while lo < hi:
mid = (lo + hi) // 2
trips = sum(mid // t for t in time)
if trips >= total_trips:
hi = mid
else:
lo = mid + 1
return lofunction minimumTime(time, totalTrips) {
let lo = 1n, hi = BigInt(Math.min(...time)) * BigInt(totalTrips);
while (lo < hi) {
const mid = (lo + hi) / 2n;
let trips = 0n;
for (const t of time) trips += mid / BigInt(t);
if (trips >= BigInt(totalTrips)) hi = mid;
else lo = mid + 1n;
}
return Number(lo);
}class Solution {
public long minimumTime(int[] time, int totalTrips) {
long lo = 1, hi = (long) java.util.Arrays.stream(time).min().getAsInt() * (long) totalTrips;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
long trips = 0;
for (int t : time) trips += mid / t;
if (trips >= totalTrips) hi = mid;
else lo = mid + 1;
}
return lo;
}
}long long minimumTime(vector<int>& time, int totalTrips) {
long long lo = 1, hi = (long long) *min_element(time.begin(), time.end()) * totalTrips;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
long long trips = 0;
for (int t : time) trips += mid / t;
if (trips >= totalTrips) hi = mid;
else lo = mid + 1;
}
return lo;
}Explanation
Given more time, the buses can only complete more trips, never fewer. So "can the buses make totalTrips within time t?" is monotone, and we binary-search the time t.
The buses run in parallel, so in time t a bus that takes time[i] per trip completes t // time[i] trips. Summing t // time[i] over all buses gives the total trips done by time t.
If that total is >= totalTrips, time t is enough so we shrink (hi = mid); otherwise we need more time (lo = mid + 1). A safe upper bound is min(time) * totalTrips, since the fastest bus alone could do all the trips by then.
Example: time = [1,2,3], totalTrips = 5. At t = 3: bus0 does 3//1 = 3, bus1 does 3//2 = 1, bus2 does 3//3 = 1, totaling 5, and no smaller t reaches 5. So the answer is 3.
The loop ends when lo == hi, landing on the smallest sufficient time.