Lyft Taxi Scheduling

Moderate
0/80
profile
Contributed by
0 upvote
Asked in company
Wells Fargo

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
10 5
1 3 5 7 8
3 3
3 4 8
Sample Output 1 :
7
6
Explanation Of Sample Input 1 :
For test case one:
‘X=10’, ‘N=5’, and ‘taxiTravelTime=[1, 3, 5, 7, 8]’, then the answer is 7. This is because the first taxi (index 0, cost 1) can make seven trips costing a total of 7 minutes, the second taxi can make two trips costing 6 minutes, and the third taxi can make one trip costing 5 minutes. Hence, we can make a total of 10 trips in 7 minutes. 
Hence, the answer to this test case will be 7.
For test case Two:
‘X=3’, ‘N=3’, and ‘taxiTravelTime=[ 3, 4, 8]’, then the answer is 6. This is because the first taxi (index 0, cost 3) can make two trips costing 6 minutes, and the second taxi can make one trip costing 4 minutes. Hence, we can make a total of 2 trips in 6 minutes. 
Hence, the answer to this test case will be 6.
Sample Input 2 :
2
15 4
5 6 9 10
6 2
13 15
Sample Output 2 :
30
45
Hint

Can we sort the ‘taxiTravelTime’ array and solve the problem greedily?

Approaches (2)
Linear Search + Greedy

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.
Time Complexity

O(Z * N). Where ‘Z’ is the (number of trips * minimum trip time) and ‘N’ is the number of Taxis. 

 

We apply linear search until we find the minimum time to complete ‘X’ trips. The upper bound to the search is ‘Z’. Hence, the overall complexity will be O(Z*N).

Space Complexity

O(1) 

 

We are using only variables that take a constant space. So, the Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Lyft Taxi Scheduling
Full screen
Console