Assign the Minimum Fleet to Rental Reservations

## Problem A rental company receives reservations. Each reservation has a unique 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 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 increasing reservation ID under ordinal ASCII order. 2. When several vehicles are available, use the smallest vehicle number. 3. When no vehicle is available, create the next consecutive vehicle number. ### Portable Function Contract Implement `assignRentalFleet(reservations)`. `reservations` is a list of string rows. Each row has exactly three fields: ```text [reservationId, pickupText, returnText] ``` - `reservationId` is a unique nonempty ASCII string. - `pickupText` and `returnText` are canonical signed 64-bit decimal integers: `"0"`, a nonzero digit followed by digits, or `"-"` followed by a nonzero digit and then zero or more digits. - Parse times exactly; every reservation satisfies `pickup < return`. - Ordinal ASCII ordering compares unsigned character values lexicographically, with a shorter prefix first. Return one list of string rows. The first row is exactly: ```text ["fleet", fleetSizeText] ``` Each later row is: ```text ["assignment", reservationId, vehicleNumberText] ``` Assignment rows are sorted by reservation ID under the same ordinal ASCII order. Counts and vehicle numbers use canonical nonnegative decimal text. The uniform string rows are the public console representation. ### Constraints & Assumptions - `0 <= len(reservations) <= 200,000`. - IDs are unique nonempty ASCII strings. - Pickup and return are signed 64-bit integers encoded canonically, with `pickup < return`. - A vehicle handles at most one reservation at any instant. - The returned assignment follows the exact 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 tagged assignment rows too. - How are simultaneously available vehicles chosen? Smallest vehicle number. - Can reservations arrive unsorted? Yes. - Why are times and results strings? Uniform string rows preserve full signed 64-bit timestamps and map directly to all four console languages. ```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"] ] return [ ["fleet", "2"], ["assignment", "r1", "1"], ["assignment", "r2", "1"], ["assignment", "r3", "2"], ["assignment", "r4", "2"] ] ``` ### Evaluation Focus - Parses full signed 64-bit timestamp text exactly. - Releases every vehicle available at a pickup time before assigning. - Uses the minimum fleet and exact smallest-vehicle rule. - Applies ordinal ASCII ordering consistently instead of locale-dependent comparison. - Emits only the tagged homogeneous string-row result. - 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?