Problem overview
The function minTime receives a slice cabTripTime, where cab i needs cabTripTime[i] minutes for any trip, and a number of trips n. All cabs can drive at the same time and there is no waiting between trips. The function returns the least number of minutes in which n trips can be finished.
With n = 3 and cabTripTime = [1, 2] the answer is 2. After 1 minute only the first cab has finished a trip, which is 1 trip in total. After 2 minutes the first cab has made 2 trips and the second 1, which is 3. With n = 10 and [1, 3, 5, 7] the answer is 7: after 6 minutes the cabs have done at most 6 + 2 + 1 + 0 = 9 trips, and after 7 minutes they have done 7 + 2 + 1 + 1 = 11.
The statement asks for O(m log T) time, where m is the number of cabs and T = n * min(cabTripTime), using O(1) extra space. A cab with trip time 0 finishes any number of trips instantly, so the answer is then 0.
Approach: binary search on the time
It is hard to schedule the trips directly, but it is easy to ask a yes-or-no question: can the cabs finish n trips within t minutes? A cab with trip time v finishes t / v whole trips in t minutes, rounded down, because a trip cut off by the deadline does not count. Add that over all cabs, and the answer to the question is whether the total reaches n.
That check is monotonic. If t minutes are enough, so is any larger time, since the cabs only complete more trips. A monotonic yes-or-no question over a range of integers is exactly what binary search handles: find the smallest t for which the answer is yes.
The search range needs a start and an end. The time cannot be below 1 (the trip times are positive in the cases that reach the search). It never needs to exceed n * min(cabTripTime), because the fastest cab alone finishes n trips in that time. That upper bound is the lesson's T. A linear scan over all times from 1 to T would cost O(m * T); halving the range each time brings it to O(m log T).
Step by step
The starter code already contains the search; the lesson's steps write the feasibility check.
- Define a closure named
hasSolutioninsideminTimewith the parameters(cabTripTime []int, n int, time int), returningbool. The binary search will call it to test each candidate time. - Declare
s, the total number of finished trips, starting at 0. - Loop over the cabs with
range, ignoring the index with_and naming each trip timev: how many minutes one trip of that cab takes. - Add
time / vtosinside the loop. Integer division throws away the unfinished part of the last trip, which is what is wanted. - Return
s >= n: the time is enough when at leastntrips are finished.
The search around it works like this. It finds the smallest minute count for which the check is true: left and right bound the candidates, mid is tested, and a successful mid is recorded in result before the search moves left to look for something smaller. A failed mid moves the search right.
The solution in Go
func minTime(cabTripTime []int, n int) int {
hasSolution := func(cabTripTime []int, n int, time int) bool {
s := 0
for _, v := range cabTripTime {
s += time / v
}
return s >= n
}
minTrip := cabTripTime[0]
for _, v := range cabTripTime {
minTrip = min(minTrip, v)
}
result, left, right := 0, 1, n*minTrip
for left <= right {
mid := (left + right) >> 1
if hasSolution(cabTripTime, n, mid) {
result = mid
right = mid - 1
} else {
left = mid + 1
}
}
return result
}
Go details worth a closer look:
- Closures.
hasSolution := func(...) bool { ... }is a function value stored in a variable. It is declared before use and could be called like any function. - Parameter names inside the closure. The closure's
cabTripTimeandnshadow the outer ones. The call passes the same values in, so they agree. - Integer division. For positive integers
time / vrounds down, so7 / 2is 3. - Multiple assignment.
result, left, right := 0, 1, n*minTripdeclares all three at once. (left + right) >> 1is the midpoint, a right shift by one bit, which divides by two. The sum is at most about 4 × 10^8 by the constraints, far below the 64-bit limit.- Built-in
min. Since Go 1.21,minis built in; it finds the fastest cab's trip time. resultstarts at 0. If some cab has trip time 0, thenrightis 0, the loop never runs, and the function returns 0 without ever dividing by zero.
Complexity
Time: O(m log T). The search range has T = n * min(cabTripTime) values, so it takes about log T rounds, and each round runs hasSolution in O(m). The scan for the minimum adds another O(m).
Space: O(1). A few integers and the closure are all that is stored.
Edge cases and common mistakes
- A cab with trip time 0. The answer is 0. Dividing by 0 would panic with an integer divide by zero error, but
hasSolutionis never called in that case, as shown above. - One cab.
cabTripTime = [5]withn = 4gives 20: the only cab drives all the trips. - Fewer than a full trip. With
[3, 3]andn = 3the answer is 6, not 4.5: after 3 minutes two trips are done, and the third needs the next full 3 minutes. Time is whole minutes, and unfinished trips never count. - Recording the answer. When the check succeeds,
resultis saved and the search continues on the left half. Returning at the first success would give a time that may not be the smallest. - The loop condition.
left <= rightkeeps the last remaining candidate in play. With<the case where the answer equalsleftandrightwould be missed. - Using the slowest cab. The upper bound comes from the fastest cab, which gives the smallest safe limit. Using the slowest cab's time would still be correct but a much larger range.
Testing
cabTripTime = [1, 2],n = 3gives 2.cabTripTime = [1, 3, 5, 7],n = 10gives 7.cabTripTime = [5],n = 4gives 20.cabTripTime = [3, 3],n = 3gives 6.cabTripTime = [0, 3],n = 7gives 0.
