Start learning free

LESSON 286 OF 441 · BINARY SEARCH

Uber Rides in C#: Binary Search on the Answer in O(m log T)

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

    C# · BINARY SEARCH

    Uber Rides in C#, explained

    Problem overview

    You get an int[] named cabTripTime, where element i is the number of minutes the i-th cab needs for one trip, and a number of trips n. Cabs work in parallel, each one starts its next trip as soon as it finishes the previous one, and there is no waiting. MinTime returns the smallest number of minutes after which at least n trips are completed in total.

    For n = 3 and cabTripTime = [1, 2] the answer is 2. After 1 minute the first cab has done 1 trip and the second none, which is 1 in total. After 2 minutes the first cab has done 2 trips and the second 1, which is 3. For n = 10 and [1, 3, 5, 7] the answer is 7: after 6 minutes the cabs have done 6 + 2 + 1 + 0 = 9 trips, after 7 minutes 7 + 2 + 1 + 1 = 11.

    If any cab has a trip time of 0, it finishes every trip instantly and the answer is 0.

    Approach: binary search on the time

    Instead of simulating the cabs, ask a yes/no question about a candidate time t: can the cabs complete at least n trips within t minutes? A cab with trip time v completes t / v trips (integer division, dropping the unfinished trip). Adding that over all cabs gives the total for t.

    The total never goes down as t grows, so the answers to the question look like no, no, no, yes, yes, yes. We want the first yes. That shape is exactly what binary search handles: test the middle time, and discard the half that can't contain the first yes.

    The search range runs from 1 to n * min(cabTripTime). The upper end is always enough: the fastest cab alone finishes n trips in n * min minutes. This is why the statement calls T = n * min(cabTripTime) the longest time worth trying. The search takes about log T rounds, and each round adds up m divisions, giving O(m log T).

    Take n = 3 and [1, 2]. The range is 1 to 3. The middle, 2, is feasible (3 trips), so record 2 and search 1 to 1. Time 1 gives only 1 trip, so the search ends with 2.

    Step by step

    The lesson provides MinTime, which does the binary search, and asks for the helper that answers the yes/no question.

    1. Declare HasSolution(int[] cabTripTime, int n, int time) above MinTime. It returns a bool: whether n trips fit in time minutes.
    2. Start a counter s at 0, as a long. It counts completed trips, and the last bullet below explains why it needs 64 bits.
    3. Open the loop over the cabs. Write a foreach over cabTripTime with an int named v, and its closing brace at once.
    4. Add each cab's trips. Inside the loop, add time / v to s. Integer division truncates, which is right: a trip that isn't finished doesn't count.
    5. Return s >= n.

    The given MinTime then does the rest. It takes the smallest trip time, sets the range to left = 1 and right = n * minTime, and loops while left <= right. For the middle value, if HasSolution says yes, the middle is recorded in result and the search continues on the left half (right = mid - 1) in case an earlier time also works. If it says no, the search moves to the right half (left = mid + 1). The last recorded value is the smallest feasible time.

    The solution in C#

    class Solution {
    public bool HasSolution(int[] cabTripTime, int n, int time) {
        long s = 0;
        foreach (int v in cabTripTime) {
            s += time / v;
        }
        return s >= n;
    }
    public int MinTime(int[] cabTripTime, int n) {
        int minTime = cabTripTime.Min();
        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 knowing:

    • Integer division truncates. With int operands, 6 / 5 is 1, 4 / 5 is 0, and -7 / 2 is -3 (toward zero). Here both operands are non-negative, so it simply drops the fraction.
    • Dividing by zero throws. time / v with v == 0 throws a DivideByZeroException for ints. The solution avoids it without a check: when some cab has a trip time of 0, Min() returns 0, so right is 0, left <= right is false at once, and the method returns 0 before HasSolution is ever called.
    • Min() comes from LINQ. It is an extension method on arrays and lists, in System.Linq, so a standalone file needs using System.Linq;. It throws an InvalidOperationException on an empty array, which the constraints rule out.
    • (left + right) >> 1 is the midpoint: a right shift by one bit halves a non-negative int. With right at most 200 million, the sum fits in an int.
    • Several declarations on one line. int result = 0, left = 1, right = n * minTime; declares three int variables, and the last initializer can use n and minTime.
    • Integer overflow doesn't throw. By default, an int that goes past 2,147,483,647 wraps around to a negative number without any error. This matters for s: it adds time / v over every cab, so with enough cabs the sum leaves the int range. With a million cabs that each take 1 minute, a time of 1,000,000 minutes gives 1,000,000,000,000 trips: an int counter would end that loop at -727379968, while the long ends at 1000000000000. That is why s is a long. The addition widens the int quotient to long, and s >= n works because n converts to long automatically. With those cabs and n = 2000000, MinTime returns 2.

    Complexity

    Let m be the number of cabs and T = n * min(cabTripTime).

    Time: O(m log T). The search range has T values and halves every round, so there are about log T rounds. Each round calls HasSolution, which makes one pass over the m cabs. Finding the minimum before the search costs one more pass, O(m).

    Space: O(1). The method uses a handful of integers.

    Edge cases and common mistakes

    • A cab with trip time 0. [0, 5] with n = 10 returns 0.
    • One cab. [5] with n = 4 returns 20: the cab needs 5 minutes per trip, and the search range is 1 to 20.
    • One trip. [3, 3, 3] with n = 1 returns 3, since one trip takes 3 minutes on any cab.
    • Cabs that finish together. [2, 3] with n = 5 returns 6: after 6 minutes the cabs have done 3 + 2 = 5 trips, and after 5 minutes only 2 + 1 = 3.
    • Stopping at the first yes. When HasSolution is true, the answer may still be smaller. The search must keep going left and remember mid.
    • Rounding up. A cab with trip time 3 has completed 1 trip at minute 5, not 2. Rounding the division up would count unfinished trips.
    • Searching the trip count. The monotone quantity is time, not the number of trips. The answer is a time.

    Testing

    • n = 3, [1, 2] gives 2.
    • n = 10, [1, 3, 5, 7] gives 7.
    • n = 10, [0, 5] gives 0.
    • n = 4, [5] gives 20.
    • n = 5, [2, 3] gives 6.
    • 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 C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free