Meeting Rooms and Minimum Fleet Assignment

Schedule half-open intervals [start, end). A resource returned at time t may be reused immediately at t. Every interval has positive duration.

Part 1: Count the Minimum Resources

Problem Statement

Given intervals, return the smallest number of rooms or cars required. For [[0,30],[5,10],[15,20]], return 2.

Approach and Complexity

Sort by start time and retain active end times in a min-heap. Pop every interval that has ended before inserting the next one. The maximum heap size is both a lower bound from simultaneous demand and achievable by reusing freed resources. Time O(n log n); space O(n). [Source: darkinterview.com]

Reference Implementation

import heapq


def min_resources(intervals):
    active = []
    answer = 0
    for start, end in sorted(intervals):
        while active and active[0] <= start:
            heapq.heappop(active)
        heapq.heappush(active, end)
        answer = max(answer, len(active))
    return answer

Part 2: Record Each Car Assignment

Problem Statement

Each reservation is (reservation_id, pickup, return), with a unique ID. Return a dictionary from reservation ID to car ID and a list of Car objects containing each car's reservations. Any minimum-fleet assignment is valid. An optional nonnegative integer fleet limit k must cause a failure result (None) if all requests cannot be served; do not silently discard requests.

For [('A', 0, 3), ('B', 1, 2), ('C', 3, 4)], one valid assignment is {'A': 0, 'B': 1, 'C': 1}. Two cars are required; a limit of one returns None.

Approach and Complexity

Process reservations by pickup time. Keep one heap entry (next_available, car_id) per allocated car. Reuse the earliest available car when possible; otherwise allocate one. If even the earliest car is busy, all cars are busy, so another car is necessary. Time O(n log n); space O(n) including assignments. [Source: darkinterview.com]

Reference Implementation

import heapq
from dataclasses import dataclass, field


@dataclass
class Car:
    id: int
    rental_record: list = field(default_factory=list)


def assign_fleet(reservations, k=None):
    heap, cars, assignment = [], [], {}
    for rid, start, end in sorted(reservations, key=lambda r: r[1]):
        if heap and heap[0][0] <= start:
            _, cid = heapq.heappop(heap)
        else:
            if k is not None and len(cars) == k:
                return None
            cid = len(cars)
            cars.append(Car(cid))
        cars[cid].rental_record.append((rid, start, end))
        assignment[rid] = cid
        heapq.heappush(heap, (end, cid))
    return assignment, cars