Busiest Rental Car
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Busiest Rental Car
A car-rental branch receives a batch of bookings for the day. Each booking has a pickup time and a return time. The branch wants to serve **every** booking using as few cars as possible, and then report which single car ends up doing the most work.
To make the assignment fully deterministic, the branch follows this exact policy:
1. Cars are numbered `1, 2, 3, ...` in the order they are first put into service.
2. Times are integers on one timeline. A booking is the half-open interval `[start, end)`: a car returned at time `t` is immediately available for another booking that starts at time `t`.
3. Process the bookings in order of increasing `start`. Break ties by increasing `end`, and break any remaining tie by the booking's original index in the input list.
4. To serve a booking, look at all cars that are currently **free** (their most recent booking's `end` is `<= start`). Assign the booking to the free car with the **smallest car number**. If no car is free, put a brand-new car into service (it receives the next unused number) and assign the booking to it.
After all bookings are assigned, return the number of the car that served the **most bookings**. If several cars are tied for the most bookings, return the **smallest** such car number.
Write a function that takes `bookings` (a list of `[start, end)` integer intervals, `start < end`) and returns the integer car number described above. If `bookings` is empty, return `0`.
### Example
```
bookings = [
[0, 30], # index 0
[5, 10], # index 1
[15, 25], # index 2
[10, 40], # index 3
[30, 50] # index 4
]
# Sorted by (start, end, index): b0[0,30], b1[5,10], b2[15,25], b3[10,40], b4[30,50]
# b0 -> no free car -> car 1 (busy until 30)
# b1 -> no free car (car1 busy until 30) -> car 2 (busy until 10)
# b3 -> free cars at start=10: car2 (freed at 10). assign car 2 (busy until 40)
# b2 -> at start=15: car1 busy until 30, car2 busy until 40 -> no free car -> car 3 (busy until 25)
# b4 -> at start=30: car1 freed at 30, car3 freed at 25 -> smallest free = car 1 (busy until 50)
#
# Bookings per car: car1 -> {b0, b4} = 2, car2 -> {b1, b3} = 2, car3 -> {b2} = 1
# Tie between car1 and car2 at 2 bookings -> return smallest -> 1
```
Output: `1`
Quick Answer: This question evaluates a candidate's ability to simulate a resource-allocation process using interval scheduling and greedy assignment rules. It tests precision in following deterministic tie-breaking logic and tracking state across sorted events, a common way interviewers assess coding and algorithmic problem-solving skills. The problem falls under practical, implementation-heavy algorithm design rather than abstract theory.
A car-rental branch receives a batch of bookings for the day. Each booking is a half-open interval `[start, end)` (a car returned at time `t` is immediately available for a booking starting at `t`). The branch serves every booking using as few cars as possible, following this deterministic policy:
1. Cars are numbered `1, 2, 3, ...` in the order they are first put into service.
2. Process bookings in order of increasing `start`; break ties by increasing `end`, then by the booking's original index in the input list.
3. To serve a booking, look at all cars currently **free** (their most recent booking's `end <= start`) and assign it to the free car with the **smallest** number. If no car is free, put a brand-new car into service (next unused number) and assign the booking to it.
After all bookings are assigned, return the number of the car that served the **most** bookings. If several cars tie for the most bookings, return the **smallest** such car number. If `bookings` is empty, return `0`.
Write a function `solution(bookings)` that takes a list of `[start, end)` integer intervals (`start < end`) and returns the integer car number.
Constraints
- 0 <= len(bookings)
- Each booking is [start, end) with start < end
- Times are integers on a single timeline and may be negative
- A car returned at time t is free for a booking that starts exactly at t (half-open intervals)
Examples
Input: [[0, 30], [5, 10], [15, 25], [10, 40], [30, 50]]
Expected Output: 1
Explanation: Sorted order b0,b1,b3,b2,b4. b0->car1, b1->car2, b3->car2(free at 10), b2->car3, b4->car1(free at 30). Counts: car1=2, car2=2, car3=1. Tie at 2 -> smallest car -> 1.
Input: []
Expected Output: 0
Explanation: No bookings, so no car is ever put into service; return 0.
Input: [[1, 5]]
Expected Output: 1
Explanation: A single booking creates car 1, which serves it; car 1 is the busiest.
Input: [[0, 1], [1, 2], [2, 3]]
Expected Output: 1
Explanation: Each booking starts exactly when car 1 becomes free, so car 1 (freed at 1, then 2) is reused for all three -> answer 1.
Input: [[0, 10], [0, 10], [0, 10]]
Expected Output: 1
Explanation: All three overlap, so three separate cars are created, each serving one booking. Three-way tie at 1 -> smallest car -> 1.
Input: [[0, 100], [1, 2], [2, 3], [3, 4]]
Expected Output: 2
Explanation: car1 takes [0,100] and stays busy. [1,2] starts a new car 2; car 2 is then free at 2 and 3 to take [2,3] and [3,4]. Counts: car1=1, car2=3 -> answer 2.
Input: [[-5, -1], [-1, 0], [0, 5]]
Expected Output: 1
Explanation: Negative times work the same way: car 1 is freed at -1 then 0, so it is reused for all three bookings -> answer 1.
Hints
- First sort the bookings by (start, end, original index) so assignment is fully deterministic.
- Track only each car's most recent booking end and how many bookings it has served; a car is free for the current booking iff its end <= the booking's start.
- To break ties toward the smallest car number, always scan cars in increasing number order and take the first free one; create a new car only when none is free.
- For the final answer, iterate cars in increasing number order and keep a strict '>' comparison so the first (smallest-numbered) car with the max count wins ties.