Skip to content

Schedule Car Rentals

Level: L3-L5 Topics: Intervals, Sweep Line, Sorting, Scalability

Problem Statement

A car rental company receives a list of rental requests. Each request specifies a (start_time, end_time) during which a car is needed. Two rentals conflict if their time intervals overlap (a car returned at time t can be rented again at time t).

Determine the minimum number of cars the company needs to fulfill all requests simultaneously.

Background & Constraints

  • Each rental request is a half-open interval [start, end).
  • A car that is returned can immediately be rented out again.
  • All times are non-negative integers.
  • The number of rental requests can be very large (up to millions at scale).

Examples

Input: [(1,4), (2,6), (4,7), (5,8), (7,9)]

Timeline visualization:

Car 1: [1----4)     [4------7)
Car 2:    [2--------6)    [7---9)
Car 3:          [5--------8)

At time 5, three rentals are active: (2,6), (4,7), and (5,8).

Output: 3

Hints & Common Pitfalls

  • Warm-up: Start by writing a function that checks whether two individual rentals conflict. This is the building block.
  • The brute-force approach checks every pair of rentals for overlap, giving O(n^2). Think about how sorting can help.
  • Consider the sweep line technique: create events for each start and end time, sort them, and sweep through to track the maximum concurrent rentals.
  • When sorting events, a "return" event at time t should be processed before a "pickup" event at time t (since the car is available immediately).
  • The answer equals the maximum number of simultaneously active rentals at any point in time.

Follow-Up Questions

  1. Conflict detection (warm-up): Write a function bool conflicts(Rental a, Rental b) that returns true if two rentals overlap. What edge cases should you test?
  2. Optimize from O(n^2): If you started with a brute-force approach, how can you reduce it to O(n log n)? What data structure or technique helps?
  3. Testing extensions: How would you generate test cases to stress-test your solution? What invariants should your tests verify?
  4. Google scale: Suppose you have billions of rental records distributed across data centers. How would you parallelize the computation? Consider partitioning by time ranges, computing local peaks, and combining results. How would you use this for peak demand planning and fleet sizing?