Problem overview
The method minTime receives cabTripTime, an array where entry i is the number of minutes cab i needs for any trip, and n, the number of trips to complete. It returns the minimum time in which the cabs can complete all n trips. Cabs work at the same time, and a cab starts a new trip the moment it finishes the previous one.
For n = 3 and cabTripTime = [1, 2] the answer is 2. After 1 minute, the first cab has done 1 trip and the second none, which is 1 trip in total. After 2 minutes, the first cab has done 2 trips and the second 1, which is 3. For n = 10 and [1, 3, 5, 7] the answer is 7: at 6 minutes the cabs finish at most 6 + 2 + 1 + 0 = 9 trips, and at 7 minutes they finish 7 + 2 + 1 + 1 = 11.
A cab with trip time 0 finishes any number of trips instantly, so the answer is then 0. The statement asks for O(m log T) time, where m is the number of cabs and T = n * min(cabTripTime) is the longest time worth trying, with O(1) extra space.
Approach: binary search on the time
Simulating the cabs trip by trip would be slow. A better question is the reverse one: given a time t, how many trips can the cabs finish? Cab i finishes floor(t / cabTripTime[i]) trips, and the totals add up because cabs don't wait for each other.
That count never decreases as t grows. If t minutes are enough for n trips, so is any larger time. So the times split into a block that are too small followed by a block that are enough, and the answer is the first time in the second block. That is a binary search, not over an array but over the possible answers.
The search range is easy to bound. The fastest cab alone finishes n trips in n * min(cabTripTime) minutes, so the answer is at most that. The answer is at least 1 when all trip times are positive.
For n = 3 and [1, 2], the range is 1 to 3. The middle is 2, which is enough (3 trips), so remember 2 and look lower. The middle of 1 to 1 is 1, which gives only 1 trip, so look higher. The range is empty, and the remembered answer is 2.
Checking one time costs O(m), and the range has T values, so the search needs about log T checks: O(m log T) in total.
Step by step
The lesson writes the feasibility check first, as a helper arrow function inside minTime, then the search around it.
- Define
hasSolutionwithconstas an arrow function taking(cabTripTime, n, time), as the first line ofminTime. It answers whethertimeminutes are enough forntrips, and the binary search will call it. It has to come before the search, because aconstcan't be used above the line that creates it. - Declare
swithlet, starting at 0. It counts the trips finished so far. - Loop over
cabTripTimewithfor...of, naming each trip timev. Each pass looks at one cab, andvis how many minutes one of its trips takes. - Add
Math.floor(time / v)tosinside the loop. A cab with trip timevcompletes that many whole trips intimeminutes. JavaScript's/gives a fractional result, soMath.floorturns it into a whole number of trips. - Return
s >= n. The time is enough when the cabs finish at leastntrips; finishing extra trips is fine.
The rest of the method is the search itself. The shortest trip time is found with reduce and Math.min. The search then keeps left and right as the smallest and largest time still possible, starting at 1 and n * minTime, and result as the best answer found so far. Each pass takes the middle time mid. If hasSolution says mid is enough, it saves mid in result and continues in the lower half with right = mid - 1. Otherwise it continues in the upper half with left = mid + 1. When the range is empty, result is the smallest time that works.
The solution in JavaScript
class Solution {
/**
* @param {number[]} cabTripTime
* @param {number} n
* @return {number}
*/
minTime(cabTripTime, n) {
const hasSolution = (cabTripTime, n, time) => {
let s = 0
for (let v of cabTripTime) {
s += Math.floor(time / v)
}
return s >= n
}
let minTime = cabTripTime.reduce((acc, val) => acc = Math.min(acc, val), cabTripTime[0])
let result = 0, left = 1, right = n * minTime;
while (left <= right) {
let mid = (left + right) >> 1
if (hasSolution(cabTripTime, n, mid)) {
result = mid
right = mid - 1
} else {
left = mid + 1
}
}
return result
}
}Some details about JavaScript:
- Division is not integer division.
7 / 2is 3.5, soMath.floor(time / v)is needed to count whole trips. >> 1halves an integer. The operator works on 32-bit signed integers, and the sumleft + rightstays below that limit here: the constraints keepn * min(cabTripTime)at most 200,000,000, so the sum is at most 400,000,000, under 2,147,483,647. For larger ranges, useMath.floor((left + right) / 2)instead.- The helper's parameters shadow the outer ones.
hasSolutiondeclares its owncabTripTimeandn, which hide the method's parameters of the same names inside the arrow function. The call passes the same values, so nothing changes. reducewith an initial value ofcabTripTime[0]finds the minimum. It would also work withMath.min(...cabTripTime), but with up to a million elements the spread can exceed the engine's argument limit, soreduceis the safer choice.
Complexity
Each call to hasSolution loops over the m cabs, so it takes O(m). The search halves a range of about T = n * min(cabTripTime) values, so it makes O(log T) calls. Finding the minimum costs one more O(m) pass. The total is O(m log T), and the extra space is O(1).
Edge cases and common mistakes
- A cab with trip time 0. Then
min(cabTripTime)is 0, sorightis 0 and the loop never runs: the method returns 0, as the statement requires. This also meanshasSolutionnever divides by zero. - A single cab. For
n = 4and[5]the answer is 20. The range is 1 to 20, and only 20 gives 4 trips. - More cabs than trips. For
n = 1and[3, 3, 3]the answer is 3, the time of one trip. - Returning
midat the first success. A time that works is not necessarily the smallest one. The search must keep going lower, andresultstores the best time seen. - Forgetting to floor the division. Without
Math.floor, the fraction of a trip left unfinished would be counted, and the answer would be too small. - Starting
leftat 0. With positive trip times, 0 minutes gives no trips, so the lowest useful time is 1.
Testing
These inputs give these results: minTime([1, 2], 3) returns 2, minTime([1, 3, 5, 7], 10) returns 7, minTime([5], 4) returns 20, minTime([3, 3, 3], 1) returns 3 and minTime([0, 4], 10) returns 0.
