Meeting room capacity: count simultaneous demand

Keep multiplicity instead of only union coverage

A baseline checks every meeting start and counts intervals containing that time: start <= time < end. Demand can increase only at a start, so the maximum of those counts is correct. That costs O(n²) time and constant extra state. Merging intervals is not an improvement for this output: two identical meetings merge to one block but still require two rooms. The representation must preserve how many intervals are active.

Represent each meeting by two events, (start, +1) and (end, -1), then sort by time and delta. The delta tie-break processes departures before arrivals.

After each event, active is the number of starts processed minus ends processed. At a shared timestamp, intermediate departure states may be below the eventual demand, but processing departures first cannot create a false peak. The maximum after all arrivals at each timestamp is exactly simultaneous demand under the half-open contract. Any schedule needs at least that many rooms. Conversely, when a new meeting begins and fewer than that many rooms are occupied, one room is free, so that bound suffices for interchangeable rooms.

Validation and event creation take O(n), sorting O(n log n), and scanning O(n). Auxiliary space is O(n) for events and Python sorting workspace; output is one integer. Explain this lower-bound-and-construction argument rather than simply asserting that a peak is “obviously” the answer.

Follow-up 1: return actual room assignments

Predict what the count discarded: identities and availability times. Sort meetings by start with original indices, use a min-heap of busy (end, room_id) entries, and release every room whose end is at most the next start.

A second heap of free room IDs makes a smallest-ID tie rule deterministic. Keep output in original input order. Assignment needs O(n) output, while the busy/free heaps need O(capacity) state beyond sorting.

Follow-up 2: each room needs a cleanup buffer

Extend occupancy end times by the agreed nonnegative buffer before sorting; do not merely change < to <=, which models endpoint inclusion rather than elapsed cleanup time. A senior candidate tests simultaneous starts/ends and duplicate intervals. A lead candidate clarifies whether room features and room-specific buffers invalidate interchangeability; capacity alone may then be insufficient to prove that a feasible assignment exists.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/10-meeting-room-capacity
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

def _intervals(intervals):
    if not isinstance(intervals, (list, tuple)):
        raise ValueError("expected a list or tuple of intervals")
    for pair in intervals:
        if (not isinstance(pair, (list, tuple)) or len(pair) != 2
                or any(type(x) is not int for x in pair) or pair[0] >= pair[1]):
            raise ValueError("intervals require integer start < end")

def meeting_room_capacity(intervals):
    _intervals(intervals)
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
    active = best = 0
    for _, delta in sorted(events):
        active += delta
        best = max(best, active)
    return best

import random
import unittest
from solution import meeting_room_capacity

class RoomTests(unittest.TestCase):
    def test_endpoints_and_multiplicity(self):
        self.assertEqual(meeting_room_capacity([(0, 10), (5, 7), (7, 12)]), 2)
        self.assertEqual(meeting_room_capacity([(1, 2), (2, 3)]), 1)
        self.assertEqual(meeting_room_capacity([(1, 2)] * 4), 4)
        self.assertEqual(meeting_room_capacity([]), 0)
        for intervals in [[(4, 4)], [(4, 3)], [(1, False)], ["ab"], None]:
            with self.assertRaises(ValueError):
                meeting_room_capacity(intervals)

    def test_active_at_starts_oracle(self):
        rng = random.Random(110)
        for _ in range(500):
            intervals = []
            for _ in range(rng.randrange(20)):
                start = rng.randrange(-5, 10)
                intervals.append((start, start + rng.randrange(1, 8)))
            expected = max((sum(start <= time < end for start, end in intervals)
                            for time, _ in intervals), default=0)
            original = intervals[:]
            self.assertEqual(meeting_room_capacity(intervals), expected)
            self.assertEqual(intervals, original)

if __name__ == "__main__":
    unittest.main()