Start learning free

LESSON 287 OF 442 · BINARY SEARCH

Minimum Time for Cab Trips in TypeScript: Binary Search on the Answer

Practice O(n log T) Read the full explanation

Uber has several cabs. The ith cab takes cabTripTime[i] minutes to complete any trip. Your task is to find the minimum time it will take Uber to get n trips completed with these cabs. You can assume there is no waiting time in-between the trips.

Note: Different cabs can take trips simultaneously (at any time, there can be more than one cab with an ongoing trip)

Example 1:

Input: n = 3, cabTripTime = [1, 2]
Output: 2
Explanation:
Trips can be managed like this:
- Trip 1: first cab from t = 0 to t = 1;
- Trip 2: second cab from t = 0 to t = 2;
- Trip 3: first cab from t = 1 to t = 2.

All the trips can be completed in 2 minutes. In 1 minute the cabs finish only 1 + 0 = 1 trip, so the answer is 2.

Example 2:

Input: n = 10, cabTripTime = [1, 3, 5, 7]
Output: 7
Explanation:
Trips can be managed like this:
- Trip 1: 1st cab from t = 0 to t = 1;
- Trip 2: 2nd cab from t = 0 to t = 3;
- Trip 3: 3rd cab from t = 0 to t = 5;
- Trip 4: 4th cab from t = 0 to t = 7;
- Trip 5: 1st cab from t = 1 to t = 2;
- Trip 6: 1st cab from t = 2 to t = 3;
- Trip 7: 1st cab from t = 3 to t = 4;
- Trip 8: 2nd cab from t = 3 to t = 6;
- Trip 9: 1st cab from t = 4 to t = 5;
- Trip 10: 1st cab from t = 5 to t = 6.

All the trips can be completed in 7 minutes. In 6 minutes the cabs finish at most 6 + 2 + 1 + 0 = 9 trips, so the answer is 7.

Constraints:

  • 1 <= cabTripTime.length <= 106
  • 0 <= cabTripTime[i] <= 2 * 104
  • 1 <= n <= 2 * 106
  • n * min(cabTripTime) <= 2 * 108
  • A cab whose trip time is 0 finishes any number of trips instantly, so then the answer is 0.

Note:

Your algorithm should run in O(m log T) time, where m is the number of cabs and T = n * min(cabTripTime) is the longest time worth trying, and use O(1) extra space.


STEP 1 OF 5
    Ctrl + Enter to check

    TYPESCRIPT · BINARY SEARCH

    Uber Rides in TypeScript, explained

    Problem overview

    A fleet of cabs must complete n trips. Cab i needs cabTripTime[i] minutes for any trip, starts the next one right away, and all cabs work at the same time. The method minTime receives cabTripTime and n and returns the smallest number of minutes after which at least n trips are finished.

    With n = 3 and cabTripTime = [1, 2] the answer is 2. After 1 minute only the first cab has finished a trip, which makes 1 trip. After 2 minutes the first cab has made 2 trips and the second cab 1, which makes 3. 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, and after 7 minutes they have finished 7 + 2 + 1 + 1 = 11.

    The statement adds a special case: a cab with trip time 0 finishes any number of trips instantly, so the answer is then 0. The target running time is O(m log T) for m cabs, with T = n * min(cabTripTime), and O(1) extra space.

    Approach: search the time, not the trips

    Simulating the cabs trip by trip would be far too slow, since n can be 2,000,000. Turn the problem around: instead of asking how long the trips take, ask whether a given time is enough.

    For a time t, cab i finishes floor(t / cabTripTime[i]) whole trips, and the cabs work in parallel, so the fleet finishes the sum of those counts. If the sum is at least n, the time is enough.

    That question is monotonic. If t minutes are enough, then t + 1 minutes are enough too, since no cab finishes fewer trips given more time. So the times split into a block of "not enough" followed by a block of "enough", and binary search can find where the second block starts. Each check costs O(m), and the search needs about log T checks.

    The search range needs two bounds. The lower bound is 1. The upper bound is n * min(cabTripTime): the fastest cab alone could do all n trips in that time, so the answer can't be larger.

    On n = 10 and [1, 3, 5, 7], the range is 1 to 10. The middle, 5, gives 5 + 1 + 1 + 0 = 7 trips, which is not enough, so the search moves to 6 to 10. The middle, 8, gives 8 + 2 + 1 + 1 = 12, which is enough, so 8 is remembered and the search moves to 6 to 7. The middle, 6, gives 9, not enough, so the range is just 7. It gives 11, so the answer is 7.

    Step by step

    The lesson supplies the binary search in minTime and asks for the helper it calls.

    1. Declare hasSolution with the parameters cabTripTime, n and time, returning a boolean. It answers whether time minutes are enough for n trips.
    2. Create a counter s with let, starting at 0. It counts the trips finished by all cabs.
    3. Loop over the cabs with for...of, naming each trip time v.
    4. Add the cab's whole trips: time / v rounded down with Math.floor. The division keeps the fraction, and a trip that hasn't finished doesn't count.
    5. Return s >= n. true tells the search to try a shorter time, and false tells it to try a longer one.

    The binary search in minTime follows the usual pattern for "find the smallest value that works". It finds the shortest cab time, sets left = 1 and right = n * minTrip, and tries the middle. When the middle works, it is saved in result and the search continues to its left for something smaller. Otherwise the search continues to its right.

    The solution in TypeScript

    class Solution {
    hasSolution(cabTripTime: number[], n: number, time: number): boolean {
        let s = 0;
        for (const v of cabTripTime) {
            s += Math.floor(time / v);
        }
        return s >= n;
    }

    minTime(cabTripTime: number[], n: number): number {
        let minTrip = cabTripTime[0];
        for (const v of cabTripTime) {
            minTrip = Math.min(minTrip, v);
        }
        let result = 0, left = 1, right = n * minTrip;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (this.hasSolution(cabTripTime, n, mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}

    The TypeScript details to know:

    • Division gives a fraction. In TypeScript, 7 / 2 is 3.5, not 3, because number is a double. Math.floor turns it into the whole-trip count, and the same trick computes the midpoint.
    • No overflow in the midpoint. In languages with 32-bit integers, (left + right) / 2 can overflow. A number holds integers exactly up to 2^53, and here the values stay within a few hundred million.
    • The zero case works by itself. If some cab has trip time 0, minTrip is 0 and right = n * 0 = 0. Since left = 1 is already greater than right, the loop never runs and the method returns the initial result of 0. Dividing by zero would not throw in JavaScript anyway: Math.floor(7 / 0) is Infinity. It's the loop that never reaches the helper.
    • Several declarations in one let. let result = 0, left = 1, right = n * minTrip; declares three variables, and each is inferred as a number.
    • this.hasSolution. A method must be called through this from inside another method of the same class, as in this.hasSolution(...).
    • Annotations are erased. The parameter types describe the expected arguments to the compiler only. Nothing checks them at run time.

    Complexity

    Time: O(m log T). Finding the shortest trip time is one pass over the m cabs. The search range has about T = n * min(cabTripTime) values and halves on every step, so it takes about log T steps, and each step calls hasSolution, which makes one pass over the cabs.

    Space: O(1). The method keeps a few numbers, whatever the sizes of n and the array.

    Edge cases and common mistakes

    • One cab. [4] with n = 1 gives 4, and [5] with n = 3 gives 15: the one cab does all the trips one after another.
    • Equal cabs. [2, 2] with n = 5 gives 6. Each cab does 3 trips in 6 minutes, so 6 trips in all. After 4 minutes the two cabs have finished only 4 trips.
    • A zero trip time. [0, 5] with n = 4 gives 0.
    • Forgetting Math.floor. Without it, time / v counts fractions of a trip, so a time can look sufficient before the last trips have really finished.
    • Returning the middle at once. When hasSolution is true, the middle may not be the smallest working time. The search saves it and keeps looking left.
    • Dropping the = in left <= right. The range of one value would never be tested, and the search could skip the answer: for [1, 3, 5, 7] and n = 10 the last range is just 7.
    • Too small an upper bound. The upper bound must be at least the true answer. n * min(cabTripTime) always is, since the fastest cab alone could finish all n trips in that time. A smaller guess, such as the fastest trip time alone, would cut off the answer for [1, 2] and n = 3.

    Testing

    • n = 3, cabTripTime = [1, 2] gives 2.
    • n = 10, cabTripTime = [1, 3, 5, 7] gives 7.
    • n = 1, cabTripTime = [4] gives 4.
    • n = 5, cabTripTime = [2, 2] gives 6.
    • n = 4, cabTripTime = [0, 5] gives 0.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free