Start learning free

LESSON 283 OF 438 · BINARY SEARCH

Minimum Time for Cab Trips in Python: 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

    PYTHON · BINARY SEARCH

    Uber Rides in Python, explained

    Problem overview

    The method minTime receives cabTripTime, a list where the i-th cab needs cabTripTime[i] minutes for any one trip, and a number of trips n. The cabs work at the same time and never wait between trips. The method returns the smallest number of minutes after which n trips can be completed.

    With n = 3 and cabTripTime = [1, 2] the answer is 2. After 2 minutes the first cab has finished 2 trips and the second one has finished 1, which makes 3. After 1 minute only the first cab has finished a trip, so 1 minute is not enough.

    With n = 10 and [1, 3, 5, 7] the answer is 7. After 6 minutes the cabs have finished at most 6 + 2 + 1 + 0 = 9 trips, and after 7 minutes they have finished 7 + 2 + 1 + 1 = 11, which is at least 10.

    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: search for the time, not for the trips

    Simulating the cabs one trip at a time would be slow. The better idea is to turn the question around: given a time budget, how many trips fit in it? A cab with trip time v completes time // v whole trips in time minutes, and the cabs work independently, so the total is the sum over all cabs.

    That count never goes down as the budget grows. So there is a threshold: every budget below it is too small, and every budget from it upwards is enough. Finding such a threshold is a job for binary search, but over the possible answers instead of over a list of values. For each guessed budget the question is a yes or no: do at least n trips fit?

    The search range needs two ends. A budget of 1 minute is the smallest worth trying when trip times are positive. At the top, the fastest cab alone can finish all n trips in n * min(cabTripTime) minutes, so no answer is larger than that. That is the T of the statement.

    On n = 3, [1, 2], the range is 1 to 3. The middle, 2, fits 2 + 1 = 3 trips, so it works: remember 2 and look at smaller budgets, 1 to 1. A budget of 1 fits only 1 trip, so it fails and the search ends with 2.

    Step by step

    The first five items are the lesson's steps, which write the helper. The search lines that call it are already in the editor; the remaining items explain them.

    1. Define the helper hasSolution(cabTripTime, n, time) inside minTime. It answers whether n trips fit in time minutes, which is the yes or no question the search needs.
    2. Start a counter s at 0 for the number of trips finished.
    3. Loop over the trip times with a for loop and the variable v. Each pass looks at one cab, and v is how many minutes one of its trips takes.
    4. Add time // v to s inside the loop. Floor division gives the number of complete trips; a trip that would end after the budget doesn't count.
    5. Return s >= n. More trips than needed is fine, as the cabs can simply be stopped.
    6. Set up the search. result starts at 0, left at 1 and right at n * min(cabTripTime).
    7. Loop while left <= right, so a range of one budget is still tested.
    8. Take the middle with (left + right) // 2.
    9. If the middle works, store it in result and move right to mid - 1 to look for something smaller.
    10. Otherwise, move left to mid + 1, because every budget up to mid is too small.
    11. Return result, the smallest budget that was found to work.

    The solution in Python

    class Solution:
    def minTime(self, cabTripTime: List[int], n: int) -> int:
        def hasSolution(cabTripTime, n, time):
            s = 0
            for v in cabTripTime:
                s += time // v
            return s >= n
        result, left, right = 0, 1, n * min(cabTripTime)
        while left <= right:
            mid = (left + right) // 2
            if hasSolution(cabTripTime, n, mid):
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        return result

    The Python details worth a closer look:

    • Floor division. // on integers gives an integer rounded down: 7 // 3 is 2 and 3 // 5 is 0. That is exactly the number of whole trips.
    • A zero trip time never reaches the division. If any cab has trip time 0, then min(cabTripTime) is 0, so right is 0 and the loop condition 1 <= 0 is false from the start. The method returns the initial result, 0, which is the right answer. Dividing by zero would raise ZeroDivisionError, but the helper is never called in that case.
    • Nested function. hasSolution is defined inside minTime and used only there. Its parameters shadow the outer names with the same spelling, which is harmless here because they receive the same values.
    • Tuple assignment. result, left, right = 0, 1, n * min(cabTripTime) sets three variables in one line. The right side is computed first.
    • No overflow. The upper bound can reach 200,000,000 by the constraints, and Python integers have no fixed size, so the middle computation (left + right) // 2 is safe. In languages with fixed-width integers you would write left + (right - left) // 2 as a habit.

    Complexity

    Time: O(m log T). The range holds T possible budgets, and each loop pass halves it, so there are about log T passes. Each pass calls hasSolution, which visits all m cabs once. With T up to 200,000,000, that is about 28 passes.

    Space: O(1). The code keeps a few integers. The helper doesn't build any list.

    Edge cases and common mistakes

    • A zero in the list. [0, 4] with any n returns 0, without dividing by zero.
    • One cab. n = 4 and [5] returns 20: the range is 1 to 20 and only 20 fits 4 trips.
    • One trip. n = 1 and [4, 4] returns 4, the time of the fastest cab for a single trip.
    • The upper bound. Starting right at a smaller number, such as n, would be too small when trip times are large. n * min(cabTripTime) is always enough.
    • Dropping result. When a budget works you can't return it immediately, since a smaller one might work too. The search keeps the last working budget and keeps looking left.
    • Using left < right. A range with one budget would be skipped, and for n = 3 and [1, 2] the search could end without ever testing the answer 2.
    • Counting partial trips. Using time / v with true division gives a float such as 2.5, which counts half trips. The helper needs //.

    Testing

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