Car Rental Assignment
GooglePhone screenMedium
Cars are numbered 0, 1, 2, ... in the order they are first used. Each reservation is [id, pickup, return]: the assigned car is out for the half-open interval [pickup, return).
assign_cars(rentals, turnaround) returns one car number per reservation: result[i] is the car assigned to rentals[i], in the original order of rentals.
Part 1: Assign the cars
Process the reservations in order of pickup, then return, then id. For each reservation, assign the lowest-numbered car that is free at its pickup time; if no car is free, open the next unused car number.
A car that comes back at time t is free for a pickup at time t. In this part turnaround is always 0.
The number of cars used must be the smallest possible.
- Example 1
- rentals
[[1,1,4],[2,2,5],[3,4,6]]- turnaround
0- Output
[0,1,0]
Why: Rental 1 takes car 0. Rental 2 starts at 2 while car 0 is out, so it opens car 1. Rental 3 starts at 4, the moment rental 1 returns, so it reuses car 0. Two cars serve all three.
Constraints
1 <= len(rentals) <= 10^51 <= rentals[i][0] <= 10^9, and all ids are distinct0 <= rentals[i][1] < rentals[i][2] <= 10^9turnaround == 0