Efficient Cab scheduling

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.

#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;

}

Java Solution as per as @Primusa suggested algo

import java.util.Scanner;

public class EfficientCabScheduling {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] kArr = new int[k];

    for (int i = 0; i < k; i++) {
      kArr[i] = sc.nextInt();
    }

    System.out.println(solve(n, kArr));
  }

  private static int solve(int n, int[] kArr) {
    int l = 0;
    int h = Integer.MAX_VALUE;
    int m = h + (l - h) / 2;
    while (l < h) {
      m = h + (l - h) / 2;
      int trips = 0;
      for (int k : kArr) {
        trips += (m / k);
      }
      if (trips == n) {
        break;
      } else if (trips < n) {
        l = m + 1;
      } else {
        h = m - 1;
      }
    }
    return m;
  }
}

we can iterate to check number of possible trips for each min and print the min at which our total no of trip become equal to N taking N as integer and K as array of trip time of cab:

def efficientCabScheduling(N, K):
if len(K)==1:
    eftime=N*K[0]
else:
    trip=0
    eftime=0
    while trip<N:
        eftime+=1
        for ch in K:
            if eftime%ch==0:
                trip+=1


return eftime

This is the JavaScript solution for efficient cab scheduling problem by Uber.

The approach here is find a time that meets the condition for targetTrips.

This can be done by doing a binary search. Since the problem say Min - if we find a value -> just traverse backwards until target is valid.

/**
 *
 * @param {number} time
 * @param {list[number]} cabTripTime
 * @param {number} targetTrip
 * @returns {number}
 */
function targetMet(time,cabTripTime, targetTrip){
  // simply iterate over all the values until trip is met. of return the sum

    let trips = 0
    for(let i = 0;i<cabTripTime.length;i++){
        trips = trips + Math.floor((time/cabTripTime[i]))
       // break if target is found
        if(trips===targetTrip){
            return trips
        }
     // this is an optimization. Not really needed. Good for large numbers
        if(trips>targetTrip){
            return trips
        }

    }
    return trips
}

/**
 *
 * @param {number} n
 * @param {list[number]} cabTripTime
 * @returns {number}
 */
function efficientCabScheduling(n,cabTripTime){
    // rename variable for clarity
    const targetTrip = n

    //  set up for binary search
    // right bound
    let timeMax = Number.MAX_SAFE_INTEGER
    // left bound
    let timeMin = 0


    // binary search until target is found
    while(timeMin<=timeMax){
        let time = Math.floor((timeMax+timeMin)/2)
        const trips = targetMet(time,cabTripTime,targetTrip)
        if(trips===targetTrip){

            // iterate to left until you find another min
            // there are cases where the value BS found can me the max
            // problem statement say MIN
            // for example [1,2,3,3,4]
            while(targetMet((time -1),cabTripTime,targetTrip)===targetTrip){
                time --
            }
            return time

        }else{
            // binary search change bounds
            if(trips>targetTrip){
                timeMax = time -1
            }else{
                timeMin = time +1
            }
        }
    }

    return 0
}

const testCase1 = efficientCabScheduling(3,[1,2])===2
const testCase2 = efficientCabScheduling(10,[1,3,5,7])===7
const testCase3 = efficientCabScheduling(10,[1,3,5,7])===0

console.log(testCase1)
console.log(testCase2)
console.log(testCase3)

'''

Using a binary search approach here ,
i take the execution time as   l(least time) = 0 ,  r (max_time) = 10^14, 
to get the exec time = mid = (l+r )/2 
Now this mid is used to calculate the total trips by iterate over the array .
ONce the sum_of_trips > TOTAL_trips 
    we decrease  the mid by , r := mid
else:
    l = mid+1
TIME COMPLEXITY =  O( log(K) * N )
N= no. of cabs
K = max_exec_time possible , here it is 10^14

'''


import math
class Solution:
 
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        l = 0 
        r = math.pow(10, 14)
        mid = 0
        ans = r 
        while l < r :
            
            mid = int((l+r)/2) # here mid is the exec time of the total trips 
            
            ct = 0
            
            for t in time:
                ct += math.floor(mid/t)
            
            if ct >= totalTrips:
                
                ans = min(ans , mid )
                r = mid 
            else:
                l = mid+1
        return int(ans)