Garage occupancy at every timestamp

Clarify first. Each ticket [entry, exit] is an inclusive range of timestamps. A car parked on [2, 4] counts at 2, 3 and 4, and stops counting at 5. Ask these questions before you code:

• Is entry <= exit always true? Can entry == exit? A car that comes and goes at the same timestamp still counts once at that timestamp.
• Are timestamps always inside [0, n - 1]? If an exit can be past the end, clip it to n - 1.
• How big are n and the number of tickets m? This decides between the two methods below.

Brute force. For each ticket, add 1 to every timestamp from entry to exit. This is correct and easy to explain. The cost is O(m * L), where L is the average stay. In the worst case that is O(m * n), for example 10^5 cars that each stay the whole day.

Optimal: a difference array. A stay changes the count at only two places. The count goes up by 1 at entry, and it goes down by 1 at exit + 1. Record only those two changes:

1. Make delta with n + 1 zeros. The extra slot takes the exit + 1 change when exit == n - 1, so no bounds check is needed.
2. For each ticket, do delta[entry] += 1 and delta[exit + 1] -= 1.
3. Take a running sum of delta[0..n-1]. The running sum at t is the occupancy at t.

Why it works. The running sum at t equals (cars with entry <= t) minus (cars with exit + 1 <= t). Every car with exit < t also has entry < t, so the difference is exactly the number of cars with entry <= t <= exit.

Invariant. After the prefix pass reaches t, running equals the number of tickets whose range contains t. It is never negative when the input is valid, because every -1 comes after its matching +1.

When n is huge but m is small. Do not allocate n slots. Sort the 2m events, (entry, +1) and (exit + 1, -1), and sweep them. Between events the count is constant, so return runs (start, end, count) instead of one value per timestamp. This takes O(m log m) time and O(m) space.

from __future__ import annotations

from itertools import accumulate


def garage_occupancy(n: int, tickets: list[list[int]]) -> list[int]:
    """Number of cars in the garage at each timestamp 0..n-1.

    A ticket [entry, exit] counts at every t with entry <= t <= exit.
    """
    if n <= 0:
        return []
    delta = [0] * (n + 1)  # delta[n] absorbs exits at n - 1
    for entry, exit_ in tickets:
        if entry > exit_:
            raise ValueError(f"bad ticket {[entry, exit_]}: entry after exit")
        lo, hi = max(entry, 0), min(exit_, n - 1)
        if lo > hi:  # stay lies fully outside the window
            continue
        delta[lo] += 1
        delta[hi + 1] -= 1
    return list(accumulate(delta[:n]))


def occupancy_runs(tickets: list[list[int]]) -> list[tuple[int, int, int]]:
    """Sparse version for huge time ranges.

    Returns maximal runs (start, end, count), inclusive, with count > 0.
    """
    events: dict[int, int] = {}
    for entry, exit_ in tickets:
        events[entry] = events.get(entry, 0) + 1
        events[exit_ + 1] = events.get(exit_ + 1, 0) - 1
    runs: list[tuple[int, int, int]] = []
    count = 0
    times = sorted(events)
    for i, t in enumerate(times):
        count += events[t]
        if count > 0 and i + 1 < len(times):
            end = times[i + 1] - 1
            if runs and runs[-1][2] == count and runs[-1][1] == t - 1:
                runs[-1] = (runs[-1][0], end, count)  # merge equal runs
            else:
                runs.append((t, end, count))
    return runs


def peak_occupancy(n: int, tickets: list[list[int]]) -> tuple[int, int]:
    """(max count, earliest timestamp where it happens)."""
    occ = garage_occupancy(n, tickets)
    if not occ:
        return 0, -1
    best = max(occ)
    return best, occ.index(best)


if __name__ == "__main__":
    assert garage_occupancy(6, [[1, 3], [2, 2], [3, 5]]) == [0, 1, 2, 2, 1, 1]
    assert garage_occupancy(3, []) == [0, 0, 0]
    assert garage_occupancy(0, [[0, 0]]) == []
    assert garage_occupancy(4, [[0, 3], [0, 3]]) == [2, 2, 2, 2]
    assert garage_occupancy(3, [[1, 1]]) == [0, 1, 0]
    assert garage_occupancy(3, [[2, 9]]) == [0, 0, 1]
    assert occupancy_runs([[1, 3], [2, 2], [3, 5]]) == [
        (1, 1, 1), (2, 3, 2), (4, 5, 1)]
    assert occupancy_runs([[0, 1], [2, 3]]) == [(0, 3, 1)]
    assert peak_occupancy(6, [[1, 3], [2, 2], [3, 5]]) == (2, 2)
    print("ok")

• garage_occupancy: O(n + m) time and O(n) space for the difference array and the output. The brute force is O(m * n) in the worst case.
• occupancy_runs: O(m log m) time to sort the distinct event times, and O(m) space. It does not depend on n.
• peak_occupancy: O(n + m) time, O(n) space.

• n = 6, tickets = [[1, 3], [2, 2], [3, 5]] gives [0, 1, 2, 2, 1, 1].
• n = 3, no tickets, gives [0, 0, 0].
• n = 0 gives [].
• n = 4, [[0, 3], [0, 3]] gives [2, 2, 2, 2] (two cars, whole window).
• n = 3, [[1, 1]] gives [0, 1, 0] (enter and leave at the same timestamp).
• n = 3, [[2, 2]] gives [0, 0, 1] (exit at the last timestamp; the exit + 1 change goes into the extra slot).
• n = 3, [[2, 9]] gives [0, 0, 1] (exit clipped to the window).
• [[1, 2], [3, 4]]: a car leaves at 2 and another enters at 3. The count is 1 at 2 and 1 at 3. It never drops to 0 between them.
• [[3, 1]] raises ValueError.

1. Peak occupancy and when it happens. Track the max during the prefix pass. This is a common Part 2. If the garage has capacity C, return the first timestamp where the count goes above C.
2. Huge time range, few cars. Timestamps are Unix seconds over a year. Use the sorted-event sweep (occupancy_runs) and return runs instead of a dense array.
3. Many queries for the count at time t. Build the runs once, then binary search the start times. Each query is O(log m). With the dense array, a query is O(1).
4. Tickets arrive online, interleaved with queries. A difference array needs a rebuild after each update. Use a Fenwick tree over the difference array: a ticket is two point updates and "count at t" is a prefix sum, both O(log n). For range max with range add, use a segment tree with lazy propagation.
5. Open tickets. Some cars have not left yet (exit is None). Treat exit as n - 1, or as infinity in the sparse version. Also ask about bad data, such as an exit with no entry, and decide whether to drop it or report it.

Mid-level (L4)

• Gets the inclusive exit rule right. The -1 goes at exit + 1, not at exit.
• Can explain the brute force and then move to the difference array without hints.
• Handles exit == n - 1 without an index error and tests the empty and single-timestamp cases.

Senior (L5)

• Asks about input limits early and says why the difference array beats the brute force for long stays.
• Explains why the running sum is correct (entries so far minus exits so far).
• Adapts quickly to peak occupancy and to a sparse time range with the sorted-event sweep.

Staff (L6+)

• Discusses the online version: Fenwick tree for counts, lazy segment tree for range max, and when each is worth the cost.
• Raises real-data issues: open tickets, duplicate or missing scans, out-of-order events, and time zones.
• Frames the design around the queries the product needs, such as a live dashboard versus a daily report, and picks the data structure from that.