Efficient Cab scheduling

Question

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

Answer 1

#include <bits/stdc++.h>

using namespace std;

int solve(int arr[],int n,int k,int mid)

{

    int trip=0;

    for(int i=0;i<k;i++)

    {

        trip+=(mid/arr[i]);

        if(trip>=n)

        return 1;

    }

    return 0;

}

int main()

{ 

   int n, k;


   cin>>n>>k;

   int arr[k];

   for(int i=0;i<k;i++)

   {

       cin>>arr[i];

   }
    
  int ans=INT_MAX;

  int l=0,h=1e9;

  while(l<=h)

  {

      int mid=l+(h-l)/2;

      if(solve(arr,n,k,mid))

      {

          ans=mid;

          h=mid-1;
      }

      else

      {

          l=mid+1;

      }

  }

  cout<<ans;

  return 0;

}

Answer 2

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.