Problem overview
The function minTime receives a vector cabTripTime, where the i-th cab needs cabTripTime[i] minutes for any trip, and a number of trips n. It returns the least number of minutes in which the cabs can complete n trips together. Cabs work in parallel and don't wait between trips.
For n = 3 and [1, 2], the answer is 2: in 2 minutes the first cab finishes 2 trips and the second finishes 1. In 1 minute they finish only 1. For n = 10 and [1, 3, 5, 7] the answer is 7: in 6 minutes the cabs finish 6 + 2 + 1 + 0 = 9 trips, and in 7 minutes 7 + 2 + 1 + 1 = 11.
The statement sets O(m log T) time, where m is the number of cabs and T = n * min(cabTripTime), and O(1) extra space. A trip time of 0 means the answer is 0.
Approach: binary search on the time
Trying every time from 1 upward would take up to T checks. Instead, notice that the question "can all n trips be done within time minutes?" has a monotone answer. If time is enough, any larger time is enough too, because the cabs only get more minutes. So the answers over time look like no, no, no, yes, yes, yes, and the first yes can be found by binary search.
The check itself is short. In time minutes, a cab with trip time v finishes time / v whole trips, rounding down. Add this up over all cabs and compare the total with n. That costs O(m) per check.
For the upper end of the search, the fastest cab alone can do all n trips in n * min(cabTripTime) minutes, so the answer never exceeds that value. The search range is from 1 to T, which needs about log T checks, so the total is O(m log T).
Step by step
- Write the check as a lambda,
hasSolution, taking the vector,nand atime. It has no captures, so it receives everything as parameters. - Start a counter
sat 0 as the lambda's first line, as along long(see the details below for why). - Loop over the cabs with a range-based
forand anintnamedv, the minutes one trip of that cab takes. - Add
time / vtosinside the loop: the number of whole trips this cab completes. Integer division in C++ drops the fraction. - Return
s >= n: enough trips fit withintime.
The lesson's solution then uses the lambda in an ordinary binary search: it finds the smallest trip time with min_element, sets left = 1 and right = n * minTime, and keeps the best feasible time in result. When mid works, the answer is mid or something smaller, so it records mid and searches the left half. When mid doesn't work, it searches the right half.
The solution in C++
class Solution {
public:
int minTime(vector<int>& cabTripTime, int n) {
auto hasSolution = [](vector<int> &cabTripTime, int n, int time) {
long long s = 0;
for (int v : cabTripTime) {
s += time / v;
}
return s >= n;
};
int minTime = *min_element(cabTripTime.begin(), cabTripTime.end());
int result = 0, left = 1, right = n * minTime;
while (left <= right) {
int mid = (left + right) >> 1;
if (hasSolution(cabTripTime, n, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
};
The C++ details worth a closer look:
- Lambdas.
auto hasSolution = [](...) { ... };defines a function object in place. The empty brackets mean it captures nothing from the surrounding function, which is why the vector andnare passed in. The return type,bool, is deduced fromreturn s >= n. - Parameters that hide outer names. The lambda's
cabTripTimeandnare its own parameters. Because it captures nothing, they can't clash with the outer ones. The localint minTimealso has the same name as the method itself, which is allowed. min_elementreturns an iterator. The*in front reads the value it points to. The call needs a non-empty range, which the constraints guarantee.- Why
sis along long. With 1,000,000 cabs of trip time 100 andn = 2000000, the first time the search tries is about 100,000,000 minutes, where the cabs finish about 10^12 trips: far more than the largestint, 2,147,483,647. A 64-bit counter holds that count, and with it this input returns the correct answer, 200. A 32-bit counter would overflow, which is undefined behaviour for signed integers in C++.rightandmidstayintbecause the constraints keep them at or below about 4 * 10^8. - The midpoint.
(left + right) >> 1is the same as dividing by 2 for non-negative numbers. Hereleft + rightis at most about4 * 10^8, which fits in anint, since the constraints keepn * min(cabTripTime)at or below2 * 10^8. - The shortcut for 0. If the smallest trip time is 0, then
rightis 0, the loop body never runs, and the function returns 0. That also means the divisiontime / vnever sees a zero divisor. - The unused-looking
result = 0. It is the returned value when the loop doesn't run. When it does run,right = n * minTimeis always feasible, soresultis set at least once.
Complexity
Time: O(m log T). The search halves a range of size T, so it makes about log T checks, and each check loops over the m cabs. Finding the minimum adds one more pass, O(m).
Space: O(1). A few integers; the vector is passed by reference and never copied.
Edge cases and common mistakes
- One cab.
[4]withn = 3gives 12:T = 12, and 11 minutes finish only 2 trips. - Equal cabs.
[5, 5, 5]withn = 7gives 15: three cabs finish 3 trips every 5 minutes, so 3 rounds cover 9 trips and 2 rounds only 6. - A zero trip time.
[0, 5]withn = 4gives 0. A search that started without taking the minimum first would divide by zero. - A time that stops mid-trip doesn't count. Rounding down is the point:
time / vcounts only completed trips. - Stopping at the first feasible time. A feasible
midmay not be the smallest one. The search keeps going left to see whether something smaller also works. - A counter that is too small. The total number of trips over all cabs can pass what an
intholds, so the countersmust be along long. Comparing it withnis fine: theintis converted tolong longfirst.
Testing
n = 3,[1, 2]gives 2.n = 10,[1, 3, 5, 7]gives 7.n = 3,[4]gives 12.n = 7,[5, 5, 5]gives 15.n = 4,[0, 5]gives 0.n = 2000000and 1,000,000 cabs that all take 100 minutes gives 200.
