## Problem A rental company receives reservations. Each reservation has a unique string ID, a pickup time, and a return time. One vehicle can serve non-overlapping reservations, and a vehicle returned at time `t` may be reused for a pickup at the same time `t`. Assign every reservation to a vehicle while using the minimum possible number of vehicles. Vehicle numbers start at `1`. To make the assignment deterministic: 1. Process reservations by increasing pickup time, then increasing return time, then lexicographically increasing reservation ID. 2. When several vehicles are available, use the smallest vehicle number. 3. When no vehicle is available, create the next consecutive vehicle number. Return the fleet size and the assignment sorted lexicographically by reservation ID. ### Function Contract Implement `assignRentalFleet(reservations)`, where each reservation is `[reservationId, pickup, return]`. Return: ```text [fleetSize, [[reservationId, vehicleNumber], ...]] ``` ### Constraints & Assumptions - `0 <= len(reservations) <= 200,000`. - Reservation IDs are unique nonempty strings. - Pickup and return are signed 64-bit integers with `pickup < return`. - A vehicle handles at most one reservation at any instant. - The returned assignment must follow the tie rules even though other minimum-fleet assignments may exist. ### Clarifying Questions to Ask - Are intervals closed at the return boundary? No; treat them as `[pickup, return)` so equality permits reuse. - Is only the minimum count required? No, return the specified assignment too. - How are simultaneously available vehicles chosen? Smallest vehicle number. - Can reservations arrive unsorted? Yes. ```hint Track both busy and reusable vehicles A min-heap by return time releases every vehicle whose reservation has ended. A second min-heap chooses the smallest available vehicle number. ``` ### Example ```text reservations = [ ["r3", 4, 7], ["r1", 1, 5], ["r2", 5, 8], ["r4", 7, 9] ] ``` The result is: ```text [2, [["r1", 1], ["r2", 1], ["r3", 2], ["r4", 2]]] ``` ### Evaluation Focus - Releases all vehicles available at a pickup time before making the assignment. - Uses the minimum fleet and the exact deterministic vehicle-number rule. - Handles identical pickup or return times and empty input. - Runs in `O(n log n)` time and `O(n)` auxiliary space. ### Extensions to Discuss 1. How would cleaning time after each return alter interval boundaries? 2. What changes if vehicles have incompatible classes or locations? 3. How could online reservations be assigned without knowing future intervals?