Last Updated: 11 Jun, 2022
Lyft Taxi Scheduling
Moderate
Asked in company
Ninja works in a travel agency. During summers, he got a total of ‘X’ clients for a trip to a nearby waterpark. Ninja has a total of ‘N’ taxis where each taxi takes different routes to reach the destination.
Ninja has an array ‘taxiTravelTime’ representing how long it takes for each taxi (at that index of the array) to make a trip. Ninja wants to know the minimum time required to make ‘X’ trips.
Ninja wants to schedule a certain number of trips with a collection of several taxis.
You have to return the minimum time required to make ‘X’ trips.
Note :
Assume that taxis can run simultaneously and there is no waiting period between trips. There may be multiple taxis with the same time cost.
Example:
If ‘X=3’, ‘N=2’ and ‘taxiTravelTime=[1,2]’,
Then the answer is 2. This is because the first taxi (index 0, cost 1) can make two trips costing 2 minutes, and the second taxi can make a single trip costing 2 minutes simultaneously.
Input Format
First-line contains 'T,' denoting the number of Test cases.
For each Test case:
The first contains two integers, 'X' denoting the number of trips and ‘N’ representing the number of taxis available.
The second line contains ‘N’ integers denoting the ‘taxiTravelTime’ array.
Output format :
You must print the minimum required time to make ‘X’ trips.
Print the output of each test case in a new line.
Constraints :
1<= T <=10
1<= X <=10^9
1<= N <=10^5
1<= taxiTravelTime[i] <=10^9
Time Limit: 1 sec
Approaches
Approach :
- We will sort the ‘taxiTravelTime’ array according to the travel time.
- Now, we will linear search on time to find the minimum time to complete ‘X’ trips.
- For each taxi, calculate the trips it can complete within time.
- If the sum of all trips is greater than or equal to ‘X’, then we will break as we have found the optimal time.
- Else try for high time.
- Return the minimum time we can make more than or equal to ‘X’ trips.
Algorithm:
- Sort ‘taxiTravelTime’.
- ‘curTimeTaken’ = 0 , ‘numberOfTrips’ = 0
- do
- ‘curTimeTaken’ += 1
- ‘tripsMade’ = 0
- for each taxi ‘i’
- ‘tripsMade’ += ( ‘curTimeTaken’ / ‘taxiTravelTime[i]’ )
- If ‘tripsMade’ >= ‘X’
- Break.
- Return the ‘curTimeTaken’ here.
Approach :
- We will do a binary search on time to find the minimum time to complete ‘X’ trips. WHY?
- For a particular time, 'Y', if we can complete ‘N’ trips, then we are sure that for all the time stamps >= ‘Y’, we will be able to complete at least ‘X’ trips because we can use the same combination we used for a time equal to ‘Y’. So to find the minimum time, we must narrow our search to the time stamps smaller than 'Y'.
- We will sort the ‘taxiTravelTime’ array according to the position.
- Now, we will binary search on time to find the minimum time to complete ‘X’ trips.
- For each taxi, calculate the trips it can complete within time.
- If the sum of all trips is greater than or equal to ‘X’, then we update this time as the answer and try for a decreased time.
- Else try for high time.
- Return the minimum time we can make more than or equal to ‘X’ trips.
Algorithm:
- Sort ‘taxiTravelTime’.
- ‘left’ = 0, ‘right’ = ‘taxiTravelTime[0]’ * ‘X’
- ‘answer’ = ‘taxiTravelTime[0]’ * ‘X’
- while ‘left’ <= ‘right’
- ‘mid’ = ‘left’ + (‘right’ - ‘left’) / 2 , ‘possibleTime’ = ‘mid’
- ‘tripsMade’ = 0
- for each taxi ‘i’
- ‘tripsMade’ += ( ‘possibleTime’ / ‘taxiTravelTime[i]’ )
- If ‘tripsMade’ <= ‘X’
- ‘Answer’ = ‘possibleTime’ , ‘right’ = ‘mid’ - 1
- Else ‘left’ = ‘mid’+ 1
- Return the ‘answer’ here.
Similar problems
Element Count in Ranges
Easy
Posted: 9 Oct, 2025
First Digit One
Moderate
Posted: 14 Oct, 2025
Minimize Maximum Adjacent Distance
Moderate
Posted: 3 Nov, 2025
Sorted Doubly Linked List to Balanced BST
Easy
Posted: 3 Nov, 2025
Minimized Maximum of Products Distributed to Any Store
Moderate
Posted: 22 Feb, 2026