Minimum Cars for Rental Requests
Problem statement
You are given an unsorted array of rental records. Each record is [recordId, pickupTime, returnTime], where recordId uniquely identifies the rental.
A car can serve only non-overlapping rentals. Treat every rental as the half-open interval [pickupTime, returnTime), so a car returned at time t may be reused by a rental picked up at time t. A zero-duration interval [t,t) is empty: assign it to car 0 (creating car 0 if necessary) without changing that car's availability.
Assign every rental to a car while using the minimum possible number of cars. Car IDs are consecutive integers beginning at 0.
Use these deterministic rules when several minimum-car assignments are possible:
- Process records by increasing
pickupTime, then increasingreturnTime, then increasingrecordId. - Assign a zero-duration record to car
0without changing any busy or available state. - Before assigning a positive-duration record, make every car whose current rental has returned available.
- Reuse the available car with the smallest car ID. If no car is available, create the next car ID.
Return a String[] in increasing car-ID order. Each string has the form carId: recordId recordId ... and lists that car's rental IDs in assignment order. The array length is the minimum car count, and the lines also define the record-ID-to-car assignment.
Interview follow-up: a fleet limit
If the fleet contains at most K cars, the assignment becomes infeasible as soon as a positive-duration record finds no available car and K cars already exist. A production API could return the unassigned record IDs, but whether to reject a rental, delay pickup, or obtain an external car is a product decision rather than part of this judged function. For K = 0, every nonempty request set is immediately infeasible.
Function
solve(requests: int[][]) → String[]Examples
Example 1
requests = [[101, 1, 3], [102, 2, 4], [103, 4, 6]]return = ["0: 101 103", "1: 102"]Records 101 and 102 overlap, so two cars are necessary. Car 0 returns at time 3 and is available for record 103 at time 4.
Example 2
requests = [[203, 5, 7], [201, 1, 5], [202, 2, 3]]return = ["0: 201 203", "1: 202"]The input is unsorted. At time 5, both cars are available, so the smallest available ID, car 0, receives record 203.
Example 3
requests = [[11, 3, 3], [10, 3, 3], [12, 3, 4]]return = ["0: 10 11 12"]The tie rule processes record IDs 10, 11, and 12 in that order. Each zero-duration rental returns immediately, so one car serves all three records.
Constraints
1 <= requests.length <= 200000- Each row contains exactly three integers:
[recordId, pickupTime, returnTime]. 1 <= recordId <= 10^9, and all record IDs are unique.0 <= pickupTime <= returnTime <= 10^9.