Lyft Taxi Scheduling
Anonymous User
3417

Problem
You want to schedule a certain number of trips with a collection of several cabs.

Given an integer n representing a desired number of trips, and an array cabTravelTime representing your cabs and how long it takes each cab (at that index of the array) to make a trip, return the minimum time required to make n trips.

Assume that cabs can run simultaneously and there is no waiting period between trips. There may be multiple cabs with the same time cost.

Examples
If n=3 and cabTravelTime=[1,2], then the answer is 2. This is because the first cab (index 0, cost 1) can make 2 trips costing a total of 2 time units, and the second cab can make a single trip costing 2 at the same time.

n=10
cabTravelTime=[1,3,5,7,8]

  • 7 trips with cab 0 (cost 1)
  • 2 trips with cab 1 (cost 3)
  • 1 trip with cab 2 (cost 5)
    So, answer is 7 (there could be other combinations)

n=3
cabTravelTime=[3,4,8]

  • 2 trips with cab 0 (cost 6)
  • 1 trip with cab 1 (cost 4)
    Time = 6

Solution (?)

My intuition was:

  • sort the cabTravelTime array
  • use the smallest value by default
  • check as I go to see if there are any "free" trips I can add on using the larger values, if they are less than or equal to my currently accrued time (tracking how many times I've used them so as not to prematurely reuse)

This passed the some test cases but failed a bunch of others, including hidden test cases which hit the time limit. I think it's okay for the test cases I provided here but I don't remember them all. I'm unsure if my intuition or implementation was wrong, or both.

Comments (6)