Problem overview
The function min_time receives cab_trip_time, a vector where entry i is the number of minutes cab i needs for one trip, and n, the number of trips to complete. It returns the smallest number of minutes after which n trips can be finished. Cabs work at the same time, and a cab starts its next trip the moment it finishes the previous one.
Take n = 3 and cab_trip_time = [1, 2]. After 1 minute the fast cab has finished one trip and the slow one none, so 1 trip is done. After 2 minutes the fast cab has finished two trips and the slow one has finished one, so 3 trips are done. The answer is 2.
In the second example, n = 10 and cab_trip_time = [1, 3, 5, 7]. After 6 minutes the cabs finish 6 + 2 + 1 + 0 = 9 trips, one short, and after 7 minutes they finish 7 + 2 + 1 + 1 = 11. The answer is 7. If any cab has a trip time of 0, it finishes any number of trips instantly, so the answer is 0.
Approach: binary search on the answer
You could try every time 1, 2, 3, and so on until enough trips fit. That works, but the answer can be as large as n * min(cab_trip_time), so the loop would be far too slow for the largest inputs.
The better idea is to turn the question around. Instead of computing the answer directly, ask a yes or no question: can all n trips be finished within time minutes? A cab with trip time v completes time / v full trips in that budget, using integer division, so the total over all cabs answers the question.
That question is monotonic. If n trips fit in 7 minutes, they also fit in 8, because every cab can only do more. So the times split into a block of "no" answers followed by a block of "yes" answers, and the task is to find where the "yes" block starts. That is exactly what binary search does: test the middle of the range, then keep only the half that can still hold the boundary.
The search range needs two ends. The lower end is 1 minute. The upper end is n * min_time, where min_time is the fastest cab's trip time: that cab alone finishes n trips in that time, so the answer can't be larger. Each test costs one pass over the cabs, and the number of tests is about the logarithm of the range, which gives the O(m log T) bound the lesson asks for, where m is the number of cabs and T = n * min_time.
Step by step
The starter code already finds min_time, handles the zero case and runs the binary search. It calls a function named has_solution that doesn't exist yet. You write it.
- Define a closure.
has_solutiontakes atimeas ani64and returns abool. A closure fits because it can usecab_trip_timeandnfrom the surrounding function without receiving them as parameters. - Start a counter.
sis ani64set to 0. It holds the number of trips finished so far. - Loop over the cabs. Iterating over
&cab_trip_timewith the pattern&vborrows the vector and copies each number out, so the vector stays usable for the next call of the closure. - Add the cab's trips. Inside the loop, add
time / vtos. - Stop early. Still inside the loop, as soon as
sreachesnthe answer is yes, and there is no point in looking at the remaining cabs, so returntrue. - Return the final comparison. If the loop ends, the closure's last expression,
s >= n, is its result.
The solution in Rust
impl Solution {
fn min_time(cab_trip_time: Vec<i64>, n: i64) -> i64 {
let min_time = match cab_trip_time.iter().min() {
Some(&v) => v,
None => return 0,
};
// If any cab has trip time 0, it serves infinitely → answer is 0.
if min_time == 0 {
return 0;
}
let has_solution = |time: i64| -> bool {
let mut s: i64 = 0;
for &v in &cab_trip_time {
s += time / v;
if s >= n {
return true;
}
}
s >= n
};
let mut result = 0i64;
let mut left = 1i64;
let mut right = n * min_time;
while left <= right {
let mid = (left + right) >> 1;
if has_solution(mid) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
result
}
}
Details that matter in this code:
- The binary search. When
has_solution(mid)is true,midis a candidate, so the code saves it inresultand searches the smaller half. When it is false, the answer must be larger, soleftmoves up. The loop ends when the range is empty, andresultholds the smallest time that worked. returninside a closure. Thereturn trueleaves only the closure, notmin_time. That is what you want here.- Integer division.
time / von integers drops the remainder, so 7 minutes with a 3-minute trip gives 2 full trips. Dividing by zero panics, which is why the code returns 0 earlier when the smallest trip time is 0. - Why
i64. Both the counter and the times arei64.n * min_timecan reach 2 000 000 * 20 000 = 40 000 000 000, which doesn't fit in ani32. In the optimized build that the lessons use, an overflowingi32product would silently wrap, to 1345294336 in this case, and the search would run over the wrong range. (left + right) >> 1. Shifting right by one divides by two for non-negative numbers. Ini64the sum can't overflow for these limits.- The match on
min().iter().min()returns anOption, because an empty vector has no minimum. The patternSome(&v)copies the number out of the reference, and theNonearm returns 0 for an empty list.
Complexity
Time: O(m log T). Finding the minimum takes one pass, O(m). The search range has T = n * min_time values, so it halves about log T times, and each test of has_solution loops over at most m cabs. The early return only makes a test faster.
Space: O(1). The closure borrows the vector, and the rest is a handful of integers.
Edge cases and common mistakes
- A zero trip time.
[0, 3]with anynreturns 0. Without the early return,time / vwould divide by zero. - An empty vector. The function returns 0 instead of panicking on a missing minimum.
- One cab.
[5]withn = 1returns 5, and[4, 4, 4]withn = 7returns 12: three cabs finish 6 trips by minute 8 and 9 by minute 12. - Searching for any feasible time. Returning the first
midthat works gives some valid time, not the smallest one. Keep searching the lower half after each success. - Dropping the early return. The answer stays correct, but each test always visits every cab.
- Using
i32for the counter or the bounds. Large inputs overflow, and the result is wrong with no warning.
Testing
n = 3,cab_trip_time = [1, 2]gives2.n = 10,cab_trip_time = [1, 3, 5, 7]gives7.n = 1,cab_trip_time = [5]gives5.n = 7,cab_trip_time = [4, 4, 4]gives12.n = 5,cab_trip_time = [0, 3]gives0.
