Fewest Rental Cars
MediumIntervals ยท Google
Given reservations, where reservations[i] = [pickup, back], assign every reservation to a car. Two reservations on the same car must not overlap, but a car brought back at time t can be picked up again at time t.
Use as few cars as possible, numbered 1 to m. Return a list whose i-th value is the car for reservation i. Any assignment with the fewest cars is accepted.
Example 1
- Input:
- reservations = [[1, 4], [2, 5], [4, 7], [6, 8]]
- Output:
- [1, 2, 1, 2]
- Explanation
- At most two rentals run at once, so two cars suffice. Car 1 comes back at 4, exactly when reservation 2 is picked up.
Example 2
- Input:
- reservations = [[1, 5], [2, 3], [6, 8]]
- Output:
- [1, 2, 1]
- Explanation
[1, 2, 2]is equally valid.
Example 3
- Input:
- reservations = [[5, 6], [1, 3], [2, 4]]
- Output:
- [1, 1, 2]
Constraints
1 <= reservations.length <= 10^50 <= pickup < back <= 10^9pickupandbackare integers