Minimum Cars for Rental Requests

Problem Statement

You are managing a car rental platform. You receive a collection of rental requests. Each request has a unique identifier, a pickup_time, and a return_time.

A single car can serve multiple requests as long as their rental periods do not overlap. If a car is returned at time t, it is immediately cleaned and available for another customer to pick up at time t (i.e., the interval is half-open: [pickup_time, return_time)).

Write a function that calculates the minimum number of cars required to satisfy all rental requests.

Function Signature

from typing import NamedTuple

class RentalRequest(NamedTuple):
    request_id: str
    pickup_time: int
    return_time: int

def min_cars_needed(requests: list[RentalRequest]) -> int:
    pass

Input & Output Format

• Input: A list of RentalRequest objects, each containing:
  • request_id: A string representing the unique request ID.
  • pickup_time: An integer representing the pickup timestamp.
  • return_time: An integer representing the return timestamp (pickup_time < return_time).
• Output: An integer representing the minimum number of cars required.

Examples

Example 1

requests = [
    RentalRequest("req_1", 1, 5),
    RentalRequest("req_2", 5, 10),
    RentalRequest("req_3", 2, 6)
]
# Output: 2

Explanation: Car A handles req_1 from time 1 to 5, and then immediately serves req_2 starting at time 5. req_3 overlaps with req_1 between times 2 and 5, so Car B is required. Total cars needed = 2.

Example 2

requests = [
    RentalRequest("req_A", 10, 20),
    RentalRequest("req_B", 12, 18),
    RentalRequest("req_C", 15, 25),
    RentalRequest("req_D", 20, 30)
]
# Output: 3

Explanation: At time 15, req_A, req_B, and req_C are all active concurrently, requiring 3 cars. At time 20, req_A ends as req_D begins, allowing the same car to be reused. The peak concurrency is 3.

Constraints

• 0 <= len(requests) <= 100,000
• 0 <= pickup_time < return_time <= 10^9
• All request_id values are unique.

Edge Cases to Consider

• Empty input: requests is empty; return 0.
• Simultaneous boundary times: Multiple drop-offs and pickups occurring at the exact same timestamp (returns must be processed before pickups at that same timestamp).
• Identical intervals: Multiple requests with the exact same pickup_time and return_time.