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)
k_i. In your example k1=1 and k2=2, so the LCM(k1,k2)=2. Which means that the cabs can do 3 trips in 2 minutes, and then all of the cabs are available. So for example if N=14, the cabs can do 12 trips in 8 minutes, and the problem is reduced to N=2 with all the cabs available. – Hamelin