Minimum Cars for Rental Requests
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Minimum Cars for Rental Requests
You receive rental requests, each with a unique request identifier, pickup time, and return time. Every request must be served. One car may serve multiple requests whose time intervals do not overlap, and a car returned at time t may be picked up by another request at the same time. Return both a deterministic request-to-car assignment and the minimum number of cars used.
## Function Contract
Implement `assign_cars(request_ids, pickup_times, return_times) -> list[list[int]]`, where corresponding indices describe one request. Car identifiers start at 0. Process requests in ascending `(pickup_time, return_time, request_id)` order. Whenever multiple previously used cars are available, choose the smallest car identifier; when none is available, allocate the next consecutive identifier. Return `[[minimum_car_count], [request_id, car_id], ...]`, with assignment rows sorted by request identifier.
## Constraints
- 0 <= number of requests <= 200000.
- Pickup and return times are integers between 0 and 10^9.
- For every request, pickup time is strictly less than return time.
- All three input arrays have equal length, and request identifiers are unique integers between 0 and 10^9.
## Examples
```text
request_ids = [20, 10, 30], pickup_times = [1, 2, 5], return_times = [5, 4, 7]
output = [[2], [10, 1], [20, 0], [30, 0]]
```
```text
request_ids = [8, 4], pickup_times = [1, 3], return_times = [3, 5]
output = [[1], [4, 0], [8, 0]]
```
```hint Test simultaneous boundaries
Include a request whose pickup equals another request's return, plus several requests that begin together.
```
```hint Check reproducibility
The same request set in a different input order must produce the same assignment under the stated tie rules.
```
Quick Answer: You receive rental requests, each with a unique request identifier, pickup time, and return time. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Assign every rental request to a car while using the minimum number of cars. A car returned at time `t` may serve another request picked up at `t`. Process requests in ascending `(pickup_time, return_time, request_id)` order. Reuse the smallest available car identifier; otherwise allocate the next identifier starting at 0. Return `[[minimum_car_count], [request_id, car_id], ...]` with assignment rows sorted by request identifier.
Constraints
- 0 <= len(request_ids) = len(pickup_times) = len(return_times) <= 200000.
- Request identifiers are unique integers from 0 through 10^9.
- 0 <= pickup_times[i] < return_times[i] <= 10^9 for every request.
Examples
Input: ([], [], [])
Expected Output: [[0]]
Explanation: No requests need zero cars and no assignment rows.
Input: ([20, 10, 30], [1, 2, 5], [5, 4, 7])
Expected Output: [[2], [10, 1], [20, 0], [30, 0]]
Explanation: The overlapping first two requests use two cars and the boundary request reuses car 0.
Hints
- Test a pickup exactly at another request's return time and several requests that start together.
- Permute the same request records and confirm that the required assignment remains unchanged.
- Include a request for which several previously used cars are all eligible under the stated tie rule.