Problem overview
A fleet has several cabs. Cab i needs cabTripTime[i] minutes for any trip, and cabs drive at the same time. The method minTime receives cabTripTime and the number of trips n, and returns the smallest number of minutes after which the cabs can have finished n trips in total. A cab starts its next trip the moment it ends one.
With n = 3 and cabTripTime = [1, 2], the answer is 2: the first cab finishes two trips (at minutes 1 and 2) and the second finishes one (at minute 2). After 1 minute only one trip is done. With n = 10 and [1, 3, 5, 7], the answer is 7: after 6 minutes the cabs have finished 6 + 2 + 1 + 0 = 9 trips, which is not enough, and after 7 minutes they have finished 7 + 2 + 1 + 1 = 11. A cab with trip time 0 completes any number of trips instantly, so the answer is 0 then.
Approach: search the time, not the schedule
Scheduling trips to cabs one by one sounds hard. The question becomes easy if you flip it: given a time t, how many trips can the cabs finish within t minutes? Cab i finishes t / cabTripTime[i] whole trips (integer division drops an unfinished trip), and the cabs work in parallel, so the total is the sum over the cabs.
That count never goes down as t grows, so the times split into two groups: too short at the start, enough from some point on. The answer is the first time in the second group, which is exactly what binary search finds. Each step asks "are mid minutes enough?" and discards half of the possible times.
The search range is 1 to n * minTrip, where minTrip is the shortest trip time. The upper end is always enough: the fastest cab alone finishes n trips in that time. For n = 3 and [1, 2] the range is 1 to 3. The middle is 2, which gives 2 + 1 = 3 trips, enough, so the search tries the lower half. The time 1 gives 1 trip, not enough, so the answer is 2.
Step by step
- Add a helper
hasSolution, taking the trip times,nand atime, and returningBool. The_labels letminTimecall it without argument names. It answers: can the cabs finishntrips withintimeminutes? - Start a counter
sat 0 withvar. It counts the trips all the cabs finish. Swift'sIntis 64 bits, so it needs no special type. - Open the loop over the cabs with
for v in cabTripTime, wherevis one cab's trip time, and write its closing brace at once. - Inside the loop, add
time / vtos. Integer division drops the fraction, so a trip that isn't finished doesn't count. - Return
s >= n.truemeans the time is enough, so the search can try shorter;falsemeans it must try longer.
The remaining part of minTime is the binary search itself: it finds the shortest trip time, sets left = 1 and right = n * minTrip, and loops while left <= right. On a success it records mid in result and moves right below it; on a failure it moves left above it.
The solution in Swift
class Solution {
func hasSolution(_ cabTripTime: [Int], _ n: Int, _ time: Int) -> Bool {
var s = 0
for v in cabTripTime {
s += time / v
}
return s >= n
}
func minTime(_ cabTripTime: [Int], _ n: Int) -> Int {
var minTrip = cabTripTime[0]
for v in cabTripTime {
minTrip = min(minTrip, v)
}
var result = 0
var left = 1
var right = n * minTrip
while left <= right {
let mid = (left + right) / 2
if hasSolution(cabTripTime, n, mid) {
result = mid
right = mid - 1
} else {
left = mid + 1
}
}
return result
}
}
Swift details worth knowing:
- Integer division.
time / vdivides twoIntvalues and truncates toward zero, so7 / 2is 3 and1 / 3is 0. That is the number of whole trips. - Division by zero crashes. Dividing an
Intby 0 stops the program in Swift.hasSolutionis safe because a zero trip time makesminTrip0, sorightis 0, the loop condition1 <= 0is false, andminTimereturns the initialresultof 0 without calling the helper. - Overflow.
Intis 64 bits and arithmetic that overflows crashes instead of wrapping. The constraintn * min(cabTripTime) <= 2 * 10^8keepsrightandleft + rightfar from that limit. The counterscan grow much larger: with a million cabs that each take 1 minute, a time of 1,000,000 minutes gives 1,000,000,000,000 trips, which a 64-bitIntholds without trouble. With those cabs andn = 2000000,minTimereturns 2. - The helper is a method. Inside
minTimeit is called ashasSolution(cabTripTime, n, mid)withoutself., which Swift allows in a class method. - Constants.
midis aletinside the loop: it is computed once per pass.left,rightandresultchange, so they arevar.
Complexity
Time: O(m log T), where m is the number of cabs and T = n * minTrip. The binary search takes about log T rounds and every round calls hasSolution, which makes one pass over the m cabs. Finding minTrip costs one more pass.
Space: O(1). A handful of integers; the array is passed along, not copied into a new one.
Edge cases and common mistakes
- A zero trip time.
[0, 3]withn = 5gives 0, as the constraints say. - One cab.
[5]withn = 4gives 20, which isntimes its trip time. A single trip with[4, 7]andn = 1gives 4, the shortest trip. - Dividing the wrong way.
v / timewould count something unrelated; the number of trips intimeminutes istime / v. - Stopping at the first success. A time that works doesn't have to be the smallest one. The search keeps looking at the lower half after every success and keeps the last
midthat worked. - Starting the range at 0. With zero trip times excluded, 0 minutes can't finish any trips when
nis at least 1, so the search starts at 1. - Using
left < right. With a strict comparison the case where both ends meet is never tested, and answers such as[3]withn = 1(answer 3, the top of the range) would be missed. - Counting more than needed. The count may overshoot
n: the condition iss >= n, nots == n.
Testing
n = 3,[1, 2]gives 2.n = 10,[1, 3, 5, 7]gives 7.n = 4,[5]gives 20.n = 1,[3]gives 3, andn = 1,[4, 7]gives 4.n = 5,[0, 3]gives 0.n = 2000000with one million cabs that each take 1 minute gives 2.
