0

Car fleet scheduler with smallest free car ID

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Car fleet scheduler with smallest free car ID

Companies: Waymo

Difficulty: Medium

Problem statement

A car rental service receives a list of lease reservations. leases[i] = [start, end] means that lease i needs one car for the half-open interval [start, end): the car is busy from start up to, but not including, end. A car whose lease ends at time t can begin another lease at time t.

Assign a car ID to every lease using these rules:

  • Handle leases in order of start. When two leases have the same start, handle the one with the smaller index first.
  • When a lease starts, give it the smallest-numbered car that is free at that moment.
  • If no car is free, add a new car to the fleet. Car IDs start at 0 and new cars get the next unused ID (0, 1, 2, ...).

Return an array result where result[i] is the car ID given to lease i. Note that these rules always use the minimum possible number of cars.

Implement assign_cars(leases: list[list[int]]) -> list[int].

Constraints

  • 0 <= len(leases) <= 10^5
  • 0 <= start < end <= 10^9
  • leases is not necessarily sorted.

Example 1

leases = [[1, 4], [2, 6], [4, 7], [5, 9]]
Output: [0, 1, 0, 2]

Lease 0 takes car 0 and lease 1 takes car 1. Car 0 comes back at time 4, so lease 2 takes it. At time 5, cars 0 and 1 are both out, so car 2 is added for lease 3. The fleet has 3 cars.

Example 2

leases = [[6, 8], [0, 10], [2, 5], [0, 3]]
Output: [1, 0, 2, 1]

Leases 1 and 3 both start at 0. Lease 1 has the smaller index, so it gets car 0 and lease 3 gets car 1. Lease 2 starts at 2 while both cars are out, so it gets car 2. At time 6, cars 1 and 2 are both free, and lease 0 takes the smaller ID, car 1.

Approach

Clarify first. Each lease holds one car for the half-open interval [start, end). A car whose lease ends at time t can start another lease at t. Handle leases in order of start, and break ties by input index. Each lease gets the smallest-numbered car that is free when it starts. Add a new car (the next unused ID) only when no car is free. Return the car ID for each lease in input order. Confirm that IDs start at 0, that start < end, and whether the input can be empty.

Link to Meeting Rooms II. The number of cars needed is the greatest number of leases that overlap at one time. A min-heap of end times gives that number. The new part is which car each lease gets, so we need to track car identities as well as counts.

Brute force. Sort the leases. For each lease, check cars 0, 1, 2, ... and take the first one whose last lease ended at or before start. This is O(n * k), where k is the fleet size. In the worst case, when every lease overlaps, that is O(n^2). It is a good starting point because the rule is easy to check.

Optimal: two heaps.

  • busy: a min-heap of (end, car_id) for cars that are leased now.
  • free: a min-heap of car IDs that are free now.

For each lease in sorted order:

  1. Pop every busy entry with end <= start and push its car ID onto free. Use <= because the intervals are half-open.
  2. If free is not empty, pop the smallest ID. If it is empty, use next_id and add 1 to it.
  3. Push (end, car_id) onto busy and record car_id at the lease's original index.

Why it is correct. Invariant: before we handle a lease that starts at s, every car is in exactly one of busy, free, or "not created yet". free holds exactly the created cars that are idle at s. Step 1 keeps this true, because start values never go down, so a car that is free at an earlier start is still free at a later one. Popping the smallest ID from free therefore applies the rule directly. We open a new car only when every created car is busy at s. At that moment next_id + 1 leases overlap at s, so no valid schedule can use fewer cars. The fleet size is optimal.

Tie order matters. Two leases with the same start are handled by input index. The earlier one gets the smaller free ID. Releasing cars before assigning cars at the same instant is what lets a lease ending at t hand its car to a lease starting at t.

Code

import heapq


def assign_cars(leases: list[list[int]]) -> list[int]:
    """Return the car ID for each lease, in input order.

    Rules: handle leases by (start, index); a car is free at time t if its
    last lease ended at or before t (half-open intervals); take the smallest
    free car ID, or open car `next_id` when none is free.
    """
    n = len(leases)
    for s, e in leases:
        if s >= e:
            raise ValueError(f"invalid lease [{s}, {e})")

    order = sorted(range(n), key=lambda i: (leases[i][0], i))
    busy: list[tuple[int, int]] = []  # (end, car_id)
    free: list[int] = []              # idle car IDs
    next_id = 0
    result = [-1] * n

    for i in order:
        start, end = leases[i]
        while busy and busy[0][0] <= start:
            _, car = heapq.heappop(busy)
            heapq.heappush(free, car)
        if free:
            car = heapq.heappop(free)
        else:
            car = next_id
            next_id += 1
        heapq.heappush(busy, (end, car))
        result[i] = car
    return result


def fleet_size(leases: list[list[int]]) -> int:
    """Minimum number of cars: the same answer as Meeting Rooms II."""
    return max(assign_cars(leases), default=-1) + 1


def assign_cars_brute(leases: list[list[int]]) -> list[int]:
    """O(n * k) check: scan cars from 0 upward for the first free one."""
    order = sorted(range(len(leases)), key=lambda i: (leases[i][0], i))
    car_free_at: list[int] = []  # car_free_at[c] = end of c's latest lease
    result = [-1] * len(leases)
    for i in order:
        start, end = leases[i]
        for car, t in enumerate(car_free_at):
            if t <= start:
                break
        else:
            car = len(car_free_at)
            car_free_at.append(0)
        car_free_at[car] = end
        result[i] = car
    return result


if __name__ == "__main__":
    assert assign_cars([]) == []
    assert assign_cars([[0, 5]]) == [0]
    assert assign_cars([[1, 4], [2, 6], [4, 7], [5, 9]]) == [0, 1, 0, 2]
    assert assign_cars([[0, 3], [3, 6]]) == [0, 0]
    assert assign_cars([[6, 8], [0, 10], [2, 5], [0, 3]]) == [1, 0, 2, 1]
    assert assign_cars([[0, 10], [0, 10], [0, 10]]) == [0, 1, 2]
    assert assign_cars([[0, 2], [0, 5], [1, 3], [3, 4]]) == [0, 1, 2, 0]
    assert fleet_size([[1, 4], [2, 6], [4, 7], [5, 9]]) == 3
    assert fleet_size([]) == 0

    import random
    for _ in range(2000):
        m = random.randint(0, 12)
        ls = []
        for _ in range(m):
            s = random.randint(0, 15)
            ls.append([s, s + random.randint(1, 6)])
        assert assign_cars(ls) == assign_cars_brute(ls), ls
    print("ok")

Complexity

  • Sorting: O(n log n) time, O(n) space for the order.
  • Each lease is pushed onto busy once and onto free at most once, and popped from each at most once. Each heap operation is O(log k), where k is the fleet size. So the main loop is O(n log k).
  • Total: O(n log n) time and O(n) space (O(k) for the heaps plus the output).
  • fleet_size is the same cost. If you only need the count, one heap of end times is enough (Meeting Rooms II).
  • The brute force is O(n log n + n * k) time and O(k) extra space.

Test cases

  • [] -> [], fleet size 0.
  • [[0, 5]] -> [0].
  • [[1, 4], [2, 6], [4, 7], [5, 9]] -> [0, 1, 0, 2]. Car 0 comes back at 4 and goes straight out again. At 5, cars 0 and 1 are both busy, so car 2 opens. Fleet size 3.
  • Back to back, [[0, 3], [3, 6]] -> [0, 0]. With half-open intervals, the car is free at 3.
  • Unsorted input, [[6, 8], [0, 10], [2, 5], [0, 3]] -> [1, 0, 2, 1]. Leases 1 and 3 both start at 0, so index 1 gets car 0. Car 1 is free at 3, so the lease at 6 takes car 1 (smaller than car 2, which is also free).
  • All overlapping, [[0, 10], [0, 10], [0, 10]] -> [0, 1, 2].
  • Smallest free ID wins, [[0, 2], [0, 5], [1, 3], [3, 4]] -> [0, 1, 2, 0]. At time 3, cars 0 and 2 are free, and car 0 is chosen.
  • Invalid lease [[5, 5]] -> ValueError (or whatever the interviewer specifies for zero-length leases).
  • Random tests: the two-heap version matches the brute force on 2,000 random inputs.

Follow-ups

  1. Fleet size only, or the busiest time. Use one heap of end times, or a sweep over +1/-1 events sorted with ends before starts at the same time. Record the time when the count reaches its peak.
  2. Online bookings. Leases arrive in start-time order as a stream. Keep busy, free, and next_id as object state and run one loop step per call to book(start, end). Each call is O(log k) amortized. If bookings can arrive out of order, the greedy no longer works. Keep a sorted interval list for each car (or a balanced tree) and check a candidate car in O(log m).
  3. Fixed fleet of k cars. Return which leases cannot be served. Reject a lease when free is empty and next_id == k. To serve as many leases as possible instead, use the classic greedy: sort by end time, and give each lease the free car whose last end is the latest one at or before start. That needs a sorted structure, not a heap.
  4. Cleaning or charging gap. A car needs g minutes between leases. Push end + g onto busy instead of end. Nothing else changes.
  5. Cancellations, or "which car is lease X in at time t?". Keep lease -> car and each car's sorted list of intervals. A cancellation removes one interval. Later assignments do not have to change, but if the rules require the smallest-ID result, recompute from the cancellation time onward.

Interviewer expectations

Mid-level (L4)

  • Asks about half-open intervals, the tie-breaking rule, and the ID base before coding.
  • Sees the link to Meeting Rooms II and writes a working heap solution, or a correct brute force that they then improve.
  • Returns answers in input order and handles empty input and back-to-back leases.

Senior (L5)

  • Gets to the two-heap solution quickly and explains why releasing before assigning at the same time is correct.
  • States the invariant and proves the fleet is minimal (when a new car opens, next_id + 1 leases overlap).
  • Tests with ties, unsorted input, and a randomized check against the brute force. Gives exact complexity in terms of n and k.

Staff (L6+)

  • Wraps the logic in an online scheduler and says clearly when the greedy stops being valid (out-of-order bookings, cancellations).
  • Covers the fixed-fleet and maximum-served variants and changes the data structure to suit them.
  • Talks about the real system: cars in different places, charging or cleaning gaps, overbooking buffers, and keeping the assignment stable for customers when the plan changes.

Sign in to comment, vote or remix.