You work as a taxi dispatcher. People will contact you to order a taxi, informing you of their pickup and drop-off times. Taxis can only service one customer at a time. They can pick up a new customer 1 time unit after it has dropped off a previous customer. What is the minimum number of taxis you need to service all requests?
Let N be the number of customer requests:
N is an integer in the range [1, 100k]
All times will be integers in range [1, 10k]
Let PU be the time of pickup and DO be the time of drop-off
For each request: PU < DO
The input list is NOT sorted.
Two customers, overlapping schedule. Two taxis needed.
requests = [(1, 4), (2, 6)]
min_num_taxis(requests) # => 2
Two customers, no overlap in schedule. Only one taxi needed.
requests = [(1, 4), (5, 9)]
min_num_taxis(requests) # => 1
2: [(1,4), (5, 9)]
3: [(1,4), (2, 9), (3, 6), (5, 8)]
Good luck and have fun!
Want to propose a challenge idea for a future post? Email firstname.lastname@example.org with your suggestions!