I came across this technical question while preparation. There are K cabs. ith cab takes ki minutes to complete any trip. What is the minimum time it will take to complete N trips with these K cabs. We can assume there is no waiting time in between trips, and different cabs can take trips simultaneously. Can anyone suggest efficient algorithm to solve this.
Example:
Input:
N=3 K=2
K1 takes 1 minute, K2 takes 2 minutes
Output:
2 minutes
Explanation: Both cabs starts trip at t=0. At t=1, first cab starts third trip. So by t=2, required 3 trips will be completed
Binary search seems pretty intuitive and simple. Let's reframe the question:
Given a time
t, compute the maximum number of trips that can be taken.
We can do this in O(K). Consider that each cab i can take up to t / k_i trips in t time, and we can simply get the sum of all t / k_i for each i to get the maximum number of trips taken in t time. This lets us build a function we can binary search over:
def f(time):
n_trips = 0
for trip_time in cabs:
n_trips += time // trip_time
return n_trips
Obviously it follows that as we increase the amount of time, the amount of trips we can take will also increase, so f(x) is non-decreasing, which means we can run a binary search on it.
We binary search for the minimum t that gives N or more trips as the output, and this can be done in O(KlogW), where W is the range of all t we have to consider.