This post is completed by 2 users

  • 1
 Add to List
Hard

559. Minimizing Taxis for Maximum Efficiency

Share Taxi Scheduling Problem

Imagine you manage a Share Taxi company. You have a wealth of historical trip data, including trip IDs, start times, and end times. Your goal is to determine the minimum number of taxis required to service all these trips without any taxi being double-booked. Additionally, you want to assign each trip to a specific taxi for optimal scheduling.

Example 1:

Trips:
Trip: A, Start Time: 1, End Time: 5
Trip: B, Start Time: 2, End Time: 10
Trip: C, Start Time: 5, End Time: 7
Trip: D, Start Time: 6, End Time: 8
Trip: E, Start Time: 7, End Time: 9

Output:
Minimum Number of Taxis Required: 3

Taxi 1: Trips: [A, C, E]
Taxi 2: Trips: [B]
Taxi 3: Trips: [D]

Example 2:

Trips:

Trip: A, Start Time: 1, End Time: 4
Trip: B, Start Time: 2, End Time: 3
Trip: C, Start Time: 3, End Time: 5
Trip: D, Start Time: 5, End Time: 6
Trip: E, Start Time: 6, End Time: 8

Output:
Minimum Number of Taxis Required: 2

Taxi 1: Trips: [A, D, E]
Taxi 2: Trips: [B, C]

Example 3:

Trips:
Trip: 1, Start Time: 1, End Time: 2
Trip: 2, Start Time: 2, End Time: 3
Trip: 3, Start Time: 3, End Time: 4
Trip: 4, Start Time: 4, End Time: 5
Trip: 5, Start Time: 5, End Time: 6
Trip: 6, Start Time: 6, End Time: 7

Output:
Minimum Number of Taxis Required: 1

Taxi 1: Trips: [A, B, C, D, E, F]

Solution:

Approach: Greedy

  1. Sort the array of trips based on their start times.
  2. Use a min-heap to keep track of the end times of trips, always allowing access to the trip that finishes the earliest.
  3. For each trip:
    • If the heap is empty, a new taxi is created and the trip is assigned to it.
    • If the taxi at the head of the heap can take the trip (its end time ≤ trip's start time), the trip is assigned to this taxi and the taxi's end time is updated.
    • If the taxi cannot take the trip, a new taxi is created and the trip is assigned to it.
  4. After processing all trips, the heap will have all the taxis and their assigned trips.

Code Example:

 

Output:

[id=2, endTime=16, tripNames=[D, G]]
[id=1, endTime=18, tripNames=[B, F]]
[id=0, endTime=25, tripNames=[A, C, E]]

Related Problems: