Car Rental Optimization
Asked at:
Amazon
DESCRIPTION
Given N cars and a list of rental requests (each with pickupTime, returnTime, and id), assign cars to maximize utilization while using the minimum number of cars possible. Each car can serve multiple requests as long as they don't overlap in time. For example, if Request A returns at time 5 and Request B picks up at time 5, the same car can serve both requests.
Input:
N = 3 requests = [ {id: 1, pickup: 0, return: 5}, {id: 2, pickup: 2, return: 7}, {id: 3, pickup: 5, return: 9} ]
Output:
[ {requestId: 1, carId: 0}, {requestId: 2, carId: 1}, {requestId: 3, carId: 0} ]
Explanation: Car 0 serves requests 1 and 3 (no overlap since request 1 returns at time 5 and request 3 picks up at time 5). Car 1 serves request 2. Only 2 cars needed despite having 3 available.
Constraints:
- 1 ≤ N ≤ 10^5 (number of available cars)
- 1 ≤ requests.length ≤ 10^5
- 0 ≤ pickupTime < returnTime ≤ 10^9
- Each request has a unique id
- A car can be assigned to a new request at the exact time it's returned from a previous request
Understanding the Problem
This is an interval scheduling problem where we need to assign overlapping time intervals to resources (cars) efficiently. The challenge is determining when a car becomes available for reuse and tracking which car to assign to each request. We must process requests in a way that allows us to identify the earliest available car at any given time. The goal is to minimize the total number of cars used while ensuring every request gets assigned.
Building Intuition
A naive approach would assign a new car to each request, using requests.length cars total, which wastes resources. A better approach sorts requests by pickupTime and uses a min-heap to track when each car becomes available again. When processing a request, if any car's return time ≤ current pickup time, we can reuse that car; otherwise, we need a new car. For example, with requests [(0,5), (2,7), (5,9)], after sorting, we assign car 0 to (0,5), car 1 to (2,7), then reuse car 0 for (5,9) since it's free at time 5.
This optimization directly impacts operational costs in real-world car rental, bike-sharing, and resource allocation systems. Minimizing fleet size while meeting demand reduces capital expenditure, maintenance costs, and parking space requirements. The greedy approach with heap-based tracking provides an O(n log n) solution that scales to large fleets.
Common Pitfalls
Implementation
Request Sorting and Preprocessing
Sort all requests by pickup time to process them chronologically, which enables the greedy strategy of always assigning the earliest available car. This ensures we can identify reuse opportunities as soon as cars become free. For requests with identical pickup times, the order doesn't affect correctness since we'll check all available cars anyway. Store the original request IDs to maintain the mapping for the final output.
def sort_and_preprocess_requests(requests):"""Sort requests by pickup time for chronological processing.requests: list of tuples (pickup_time, return_time, request_id)Returns: sorted list of requests"""return sorted(requests, key=lambda x: x[0])
Car Availability Tracking with Min-Heap
Use a min-heap (priority queue) to track available cars, where each entry contains (returnTime, carId). The heap is ordered by returnTime, so the car that becomes available soonest is always at the top. When processing a request, pop all cars from the heap whose returnTime ≤ pickupTime to find reusable cars. If the heap is empty, allocate a new car with the next available ID. After assignment, push (currentReturnTime, assignedCarId) back onto the heap.
import heapqdef assign_cars(requests):requests.sort(key=lambda x: x[0]) # Sort by pickup timemin_heap = [] # (returnTime, carId)next_car_id = 0assignments = {}for pickup, return_time, req_id in requests:# Pop all cars available by pickup timewhile min_heap and min_heap[0][0] <= pickup:heapq.heappop(min_heap)# Reuse car or allocate new oneif min_heap:_, car_id = heapq.heappop(min_heap)else:car_id = next_car_idnext_car_id += 1assignments[req_id] = car_idheapq.heappush(min_heap, (return_time, car_id))return assignments
Assignment Mapping and Result Construction
Maintain a mapping from each requestId to its assigned carId as we process sorted requests. After processing all requests, construct the final output array by iterating through the original request order (not sorted order) and looking up each assignment. This ensures the output matches the input request ordering. Track the total number of unique cars used to verify we're using the minimum fleet size.
def construct_result(requests, assignments):result = []for request in requests:request_id = request[2]car_id = assignments[request_id]result.append(car_id)return result# Usage during processing:# assignments = {} # requestId -> carId mapping# for pickup, dropoff, req_id in sorted_requests:# car_id = get_available_car() # from min heap or similar# assignments[req_id] = car_id## result = construct_result(original_requests, assignments)# num_cars_used = len(set(assignments.values()))
What We've Learned
- Pattern: Interval scheduling with resource reuse - sort by start time, use min-heap to track resource availability
- Use Case: Applies to any resource allocation problem with time-bound reservations (meeting rooms, servers, vehicles)
- Optimization: Greedy assignment with heap operations achieves O(n log n) time complexity
- Edge Case: Handle same-time pickup/return correctly (≤ comparison) to maximize car reuse
Problems to Practice
hard
This problem uses a min-heap to efficiently merge multiple sorted sequences, similar to how the car rental problem uses a heap to track when cars become available. Both require managing multiple timelines and selecting the optimal next element.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late June, 2025
Senior
Mid May, 2025
Senior
Mid December, 2024
Amazon
Mid-level
Given car license plate entry and exit times, find the maximum number of cars present in a day
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.