Start learning free

LESSON 287 OF 442 · BINARY SEARCH

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

    SCALA · BINARY SEARCH

    Uber Rides in Scala, explained

    Problem overview

    The method minTime receives cabTripTime, an Array[Int] where element i is the number of minutes cab i needs for one trip, and n, the number of trips that must be completed. The cabs work at the same time and never wait between trips. The method returns the smallest number of minutes after which at least n trips are done.

    With n = 3 and cabTripTime = [1, 2], after 1 minute the first cab has finished 1 trip and the second none, so 1 trip in total. After 2 minutes the first cab has finished 2 trips and the second 1, so 3 trips in total, and the answer is 2. With n = 10 and [1, 3, 5, 7], six minutes give 6 + 2 + 1 + 0 = 9 trips, which is not enough, and seven minutes give 7 + 2 + 1 + 1 = 11, so the answer is 7.

    The statement asks for O(m log T) time, where m is the number of cabs and T = n * min(cabTripTime), and for constant extra space. A cab whose trip time is 0 finishes any number of trips instantly, and then the answer is 0.

    Approach: binary search on the answer

    Searching minute by minute would work but is slow. The problem has a structure that allows something better. Define a yes-or-no question: can the cabs finish n trips within t minutes? If the answer is yes for some t, it is also yes for every larger t, since extra time can only add trips. So the answers run no, no, no, yes, yes, yes as t grows. The task is to find the first yes, and binary search does that by checking the middle time and discarding half of the range each time.

    The question is easy to answer. Within t minutes, a cab with trip time v finishes t / v whole trips, and integer division drops an unfinished trip, which doesn't count. Adding this over all cabs gives the total, which is compared with n.

    The range to search is from 1 to n * min(cabTripTime). That upper limit always works: the fastest cab alone finishes n trips in that time.

    A worked search for n = 3 and [1, 2]: the range is 1 to 3. The middle is 2, and 2 / 1 + 2 / 2 = 3, which is enough, so remember 2 and search 1 to 1. The middle is 1, and 1 / 1 + 1 / 2 = 1, which isn't enough, so search 2 to 1, which is empty. The answer is 2.

    Step by step

    The lesson provides the search in minTime and has you write the helper it calls, hasSolution.

    1. Add the helper hasSolution(cabTripTime: Array[Int], n: Int, time: Int): Boolean, with a body in braces after =. It answers whether time minutes are enough.
    2. Create a counter s with var, starting at 0L, so it is a Long. It counts the trips all cabs finish within time, and it grows once per cab.
    3. Open the loop over the cabs with for (v <- cabTripTime), where v is that cab's minutes per trip, and write its closing brace at once.
    4. Inside the loop, add the whole trips of this cab with s += time / v. The trips of different cabs add up because the cabs work simultaneously.
    5. Return s >= n as the last expression. A true means the time is enough, so the search tries a shorter time. A false means it needs a longer one.

    In the search itself, minTime finds the fastest cab with a loop, sets left to 1 and right to n * minTrip, and keeps a result. For each middle time it asks hasSolution. On a true it records the time as a candidate answer and moves right below it, to look for something shorter. On a false it moves left above it.

    The solution in Scala

    class Solution {
    def hasSolution(cabTripTime: Array[Int], n: Int, time: Int): Boolean = {
        var s = 0L
        for (v <- cabTripTime) {
            s += time / v
        }
        s >= n
    }

    def minTime(cabTripTime: Array[Int], n: Int): Int = {
        var minTrip = cabTripTime(0)
        for (v <- cabTripTime) {
            minTrip = math.min(minTrip, v)
        }
        var result = 0
        var left = 1
        var right = n * minTrip
        while (left <= right) {
            val mid = (left + right) / 2
            if (hasSolution(cabTripTime, n, mid)) {
                result = mid
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        result
    }
}

    The Scala details worth knowing:

    • Integer division truncates. With two Ints, 7 / 3 is 2, so time / v is exactly the count of finished trips. No floor is needed.
    • Division by zero throws. Dividing an Int by a variable that holds 0 throws an ArithmeticException with the message / by zero. A cab with trip time 0 would do that inside hasSolution. The solution never gets there: when the fastest cab takes 0 minutes, right is n * 0 = 0, the condition left <= right (1 <= 0) is false at once, and the method returns the initial result, 0.
    • var versus val. s, minTrip, result, left and right all change, so they are vars. mid is fixed inside one pass of the loop, so it is a val.
    • The last expression. hasSolution ends with s >= n and minTime with result. Neither needs return.
    • (left + right) / 2. This could overflow Int if both values were near the top of the range, about 2.1 billion. Here the constraints keep right at or below 200,000,000, so the sum fits.
    • The type of the sum. The counter s is a Long, written 0L. With a very large number of cabs, the total of time / v can exceed the Int range (largest value 2,147,483,647), and an Int wraps silently. With 1,000,000 cabs that each take 1 minute, a time of 1,000,000 minutes gives a total of 1,000,000,000,000: an Int counter would end that loop at -727379968, while the Long ends at 1000000000000. In s += time / v the Int quotient is widened to Long, and s >= n compares a Long with an Int directly. With those cabs and n = 2000000, minTime returns 2.

    Complexity

    Time: O(m log T). The search range has T = n * min(cabTripTime) values, and each iteration halves it, so there are about log T iterations. Each one calls hasSolution, which loops once over the m cabs. Finding the minimum adds one more pass of O(m).

    Space: O(1). The code uses a handful of integers and does not copy the array.

    Edge cases and common mistakes

    • A single cab. With [5] and n = 1 the range is 1 to 5, and the answer is 5. With [3] and n = 4 the answer is 12, which is n * 3, the top of the range.
    • Equal cabs. [2, 2] with n = 3 gives 4: after 2 minutes two trips are done, and the third needs another round.
    • A zero trip time. [0, 5] with n = 4 gives 0, and no division by zero happens, because the loop never runs.
    • Using left < right. A range with one value, like 2 to 2, would never be checked, and the answer could be missed. Keep <=.
    • Stopping at the first yes. Finding some time that works is not enough: the task asks for the smallest. After a true, record the time and keep searching the shorter half.
    • Counting a partial trip. A trip that isn't finished within the time doesn't count. Integer division handles this. Rounding up would give wrong totals.
    • Searching from the largest cab time. The upper limit must come from the fastest cab. The slowest cab's time can be much larger than needed, and a range from the fastest cab is always large enough.

    Testing

    • n = 3, [1, 2] gives 2.
    • n = 10, [1, 3, 5, 7] gives 7.
    • n = 4, [0, 5] gives 0.
    • n = 1, [5] gives 5.
    • n = 4, [3] gives 12.
    • n = 3, [2, 2] gives 4.
    • n = 2000000 with one million cabs that each take 1 minute gives 2. This is the case that needs the Long counter.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free