Earliest time a fleet completes its trips
Vehicle i needs time[i] units of time per trip and starts its next trip as soon as one ends.
All vehicles start at time 0 and run independently. Return the smallest whole time t by which the
vehicles together have completed at least totalTrips trips.
Examples
| Input | Output | Why |
|---|---|---|
time = [1, 2, 3], totalTrips = 5 | 3 | By time 3: 3 + 1 + 1 = 5 trips. By time 2: 2 + 1 + 0 = 3. |
time = [2], totalTrips = 1 | 2 | |
time = [5, 10, 10], totalTrips = 9 | 25 | 5 + 2 + 2 = 9 by time 25. |
Constraints
- 1 ≤ time.length ≤ 10⁵
- 1 ≤ time[i], totalTrips ≤ 10⁷
Hints
Hint 1
At time t, how many trips has vehicle i finished?
Hint 2
⌊t / time[i]⌋. Add them up: the count can only grow with t.
Hint 3
Upper bound: the fastest vehicle alone finishes totalTrips trips by min(time) × totalTrips. Search [1, that] for the first t with enough trips.
Where people lose marks
- Using 32-bit integers for t: the upper bound reaches 10¹⁴.
- Assuming the sum is small. Here each term is at most totalTrips, so 64 bits suffice; stopping as soon as the target is reached keeps the check safe in variants without that bound, and costs nothing.
- Starting the search at 0 and returning 0 when totalTrips is positive: no trip ends at time 0.
Dry run on [2,3,7],10
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 7lo1hi20
Times from 1 to min(time) × 10 = 20, when the fastest vehicle alone would be done.
-
Step 2 / 7lo1mid10hi20
By time 10: 5 + 3 + 1 = 9 trips, short of 10. 10 fails, so does everything below it: lo = 11.
-
Step 3 / 7lo11mid15hi20
By time 15: 7 + 5 + 2 = 14 trips, enough 10. 15 works, so the answer is 15 or smaller: hi = 15.
-
Step 4 / 7lo11mid13hi15
By time 13: 6 + 4 + 1 = 11 trips, enough 10. 13 works, so the answer is 13 or smaller: hi = 13.
-
Step 5 / 7lo11mid12hi13
By time 12: 6 + 4 + 1 = 11 trips, enough 10. 12 works, so the answer is 12 or smaller: hi = 12.
-
Step 6 / 7lo11mid11hi12
By time 11: 5 + 3 + 1 = 9 trips, short of 10. 11 fails, so does everything below it: lo = 12.
-
Step 7 / 7answer12
lo = hi = 12: by time 12 there are 11 trips, by 11 only 9.
How to think about it
The check for a fixed time is one sum: vehicle i has finished ⌊t / time[i]⌋ trips by time
t, so the fleet has finished
trips(t) = Σ ⌊t / time[i]⌋.
Each term is non-decreasing in t, so the test trips(t) ≥ totalTrips switches from
false to true once, and the answer is the first t where it is true.
An upper bound comes from ignoring every vehicle but the fastest: on its own it finishes
totalTrips trips by min(time) × totalTrips, and the others can only help. That bound can
reach 10¹⁴, so the search variables and the sum need 64 bits. The search takes about 47 checks of O(n)
each.
Compare the eating-rate problem: there the quantity searched was a rate and the check summed ceilings; here it is a time and the check sums floors. Name what you are searching over and the check usually writes itself.
Complexity. Time O(n log(min(time) × totalTrips)) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def min_time(time, total_trips):
def enough(t):
done = 0
for x in time:
done += t // x
if done >= total_trips: # stop early
return True
return False
lo, hi = 1, min(time) * total_trips # the fastest vehicle alone is done by hi
while lo < hi:
mid = (lo + hi) // 2
if enough(mid):
hi = mid
else:
lo = mid + 1
return lo#include <vector>
#include <algorithm>
long long solve(const std::vector<int>& time, long long totalTrips) {
auto enough = [&](long long t) {
long long done = 0;
for (long long x : time) {
done += t / x;
if (done >= totalTrips) return true; // stop early
}
return false;
};
long long lo = 1, hi = (long long)*std::min_element(time.begin(), time.end()) * totalTrips;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (enough(mid)) hi = mid; else lo = mid + 1;
}
return lo;
}class Solution {
private boolean enough(int[] time, long t, long totalTrips) {
long done = 0;
for (int x : time) {
done += t / x;
if (done >= totalTrips) return true; // stop early
}
return false;
}
public long minTime(int[] time, int totalTrips) {
long fastest = Long.MAX_VALUE;
for (int x : time) fastest = Math.min(fastest, x);
long lo = 1, hi = fastest * totalTrips;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (enough(time, mid, totalTrips)) hi = mid; else lo = mid + 1;
}
return lo;
}
}function minTime(time, totalTrips) {
const enough = t => {
let done = 0;
for (const x of time) {
done += Math.floor(t / x);
if (done >= totalTrips) return true; // stop early
}
return false;
};
let lo = 1, hi = Math.min(...time) * totalTrips; // below 2^53: exact
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (enough(mid)) hi = mid; else lo = mid + 1;
}
return lo;
}fn solve(time: &[i64], total_trips: i64) -> i64 {
let enough = |t: i64| -> bool {
let mut done = 0;
for &x in time {
done += t / x;
if done >= total_trips {
return true; // stop early
}
}
false
};
let (mut lo, mut hi) = (1i64, time.iter().min().unwrap() * total_trips);
while lo < hi {
let mid = lo + (hi - lo) / 2;
if enough(mid) { hi = mid } else { lo = mid + 1 }
}
lo
}solve :: [Int] -> Int -> Int
solve time total = go 1 (minimum time * total)
where
-- the running total stops being forced once it reaches the target
enough t = any (>= total) (scanl1 (+) [t `div` x | x <- time])
go lo hi
| lo >= hi = lo
| enough mid = go lo mid
| otherwise = go (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Variants to try
- Vehicles start at different times: trips(t) = Σ ⌊max(0, t − start[i]) / time[i]⌋, still monotone.
- Each vehicle needs a rest after every trip: fold the rest into time[i].
Next problems
Smallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem → Medium20 minThe slowest rate that clears every queue in time
At rate k a queue of p items takes ⌈p / k⌉ hours. The total only falls as k rises, so search for the smallest k that fits the deadline.
Open the problem → Medium20 minThe first day enough adjacent flowers are open
Fix a day and count how many runs of k open flowers it gives, greedily. More days never close a flower, so search the first day that gives m runs.
Open the problem →Write a solution and run it against the real test table.
Keep going
Smallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem → Medium20 minThe slowest rate that clears every queue in time
At rate k a queue of p items takes ⌈p / k⌉ hours. The total only falls as k rises, so search for the smallest k that fits the deadline.
Open the problem → Medium20 minThe first day enough adjacent flowers are open
Fix a day and count how many runs of k open flowers it gives, greedily. More days never close a flower, so search the first day that gives m runs.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.