Assign the Minimum Fleet to Rental Reservations

Problem Statement

You are managing a car rental fleet. You are given a list of reservations, where reservations[i] = [pickup_i, dropoff_i] denotes the pickup and dropoff times of the i-th reservation.

A vehicle assigned to reservation i is occupied in the half-open interval [pickup_i, dropoff_i). This means the vehicle is returned and becomes available for another reservation at time dropoff_i (i.e., another customer can pick it up at pickup_j if pickup_j >= dropoff_i).

Your goal is to assign each reservation to a vehicle such that:

1. No two reservations assigned to the same vehicle overlap in time.
2. The total number of vehicles used is minimized.
3. Assignments are deterministic: reservations are processed in ascending order of their pickup time. If multiple reservations have the same pickup time, process them by their original reservation index i in ascending order.
4. When multiple vehicles are idle and available at the time of pickup, always assign the vehicle with the smallest vehicle ID (vehicles are numbered 1, 2, 3, ...). If no idle vehicle is available, assign the next smallest unused vehicle ID.

Return a tuple (fleet_size, assignments), where fleet_size is an integer representing the minimum number of vehicles needed, and assignments is a list of integers where assignments[i] is the vehicle ID assigned to reservation i.

Function Signature

def assign_fleet(reservations: list[list[int]]) -> tuple[int, list[int]]:
    pass

Constraints

• 0 <= len(reservations) <= 10^5
• 0 <= pickup_i < dropoff_i <= 10^9
• All inputs are integers.

Examples

Example 1

Input: reservations = [[1, 4], [2, 5], [4, 7], [3, 6]]
Output: (3, [1, 2, 1, 3])
Explanation:
- Reservation 0 [1, 4]: Assigned to Vehicle 1.
- Reservation 1 [2, 5]: Vehicle 1 is busy; assigned to Vehicle 2.
- Reservation 3 [3, 6]: Vehicles 1 and 2 are busy; assigned to Vehicle 3.
- Reservation 2 [4, 7]: At t = 4, Vehicle 1 is returned and becomes available. Assigned to Vehicle 1.
Fleet size is 3, assignments are [1, 2, 1, 3].

Example 2

Input: reservations = [[1, 3], [3, 5]]
Output: (1, [1, 1])
Explanation:
Vehicle 1 is returned at time 3 and can immediately be reused at time 3.

Edge Cases

• reservations is empty: return (0, []).
• Simultaneous start and end times: ensure vehicles returned at time t are freed before any new vehicle is assigned at time t.