Lab 06 — Intervals: Meeting Rooms II (Heap Of Ends + Sweep-Line Alternate)

Goal

Master the two canonical interval algorithms — min-heap of end times and event-based sweep line — applied to the same problem (LC 253). Deliverable solves it both ways, in O(N log N) time, O(N) space, and you can articulate the tie-breaking rule, why one approach is more intuitive while the other generalizes more cleanly to “max concurrent X” problems.

Background Concepts

Sorting by start time as the canonical interval-prep; min-heap of end times tracking active intervals; sweep line as event stream (time, ±1) with stable tie-breaking; the “end before start” tie-break for closed-on-start, open-on-end intervals. Review pattern Intervals and Heap.

Interview Context

Interval problems appear at Meta, Google, and Amazon — and Meeting Rooms II in particular is a top-15 most-asked Medium. The interview signal is whether you can recognize that “min number of rooms” = “max concurrent meetings”, and then compute concurrency either via heap-of-ends or sweep. Strong candidates do one approach correctly; elite candidates do both, articulate the trade-off, and handle the open/closed interval tie-break correctly without prompting.

Problem Statement

Given an array of meeting time intervals intervals[i] = [start_i, end_i], return the minimum number of meeting rooms required.

Constraints

  • 1 ≤ N ≤ 10^4
  • 0 ≤ start_i < end_i ≤ 10^6
  • Each interval is half-open [start, end): a meeting ending at time t and one starting at time t can share a room.

Clarifying Questions

  1. Are intervals half-open or closed? (Crucial: [1,3] and [3,5] — same room or not? Per LC 253, half-open: same room. This dictates the tie-break.)
  2. Can two meetings start at the same time? (Yes — they need separate rooms.)
  3. Are intervals sorted? (No assumption.)
  4. Is start < end strict? (Per constraints, yes; no zero-duration meetings.)
  5. Are room IDs significant, or just the count? (Just the count.)

Examples

InputOutput
[[0,30],[5,10],[15,20]]2
[[7,10],[2,4]]1
[[1,5],[5,10],[10,15]]1 (chained, half-open)
[[1,5],[2,5],[5,10]]2 (overlap at [2,5]; the [5,10] reuses)
[[1,2]]1

Initial Brute Force

For each pair (i, j), count overlaps; max over all time points.

def min_rooms_brute(intervals):
    times = sorted(set(t for s, e in intervals for t in (s, e)))
    best = 0
    for t in times:
        count = sum(1 for s, e in intervals if s <= t < e)  # half-open
        best = max(best, count)
    return best

Brute Force Complexity

Time O(N²). Space O(N). At N=10⁴, ~10⁸ ops — borderline; passes in C++ but TLEs in Python.

Optimization Path A — Heap of End Times

Sort intervals by start. Maintain a min-heap of end times for currently active meetings. For each new interval (start, end):

  • If the heap’s smallest end ≤ start, that room frees up — pop it.
  • Push the new end.

The number of rooms needed = max heap size ever, which equals the final heap size if we don’t pop more than we push (and we don’t, by the invariant). Actually, simpler: rooms = heap size at end, since we only pop when reusing, never net.

import heapq

def min_rooms_heap(intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []
    for s, e in intervals:
        if heap and heap[0] <= s:
            heapq.heappop(heap)        # reuse a room
        heapq.heappush(heap, e)
    return len(heap)

Optimization Path B — Sweep Line

Convert intervals to events (start, +1), (end, -1). Sort: by time, with end events before start events on ties (because [1,5] and [5,10] share a room). Sweep, tracking max concurrent.

def min_rooms_sweep(intervals):
    events = []
    for s, e in intervals:
        events.append((s, +1))
        events.append((e, -1))
    events.sort()                       # (time, +1)>(time, -1): -1 sorts first since -1 < 1
    cur = best = 0
    for _, delta in events:
        cur += delta
        best = max(best, cur)
    return best

The tie-break is automatic: (t, -1) < (t, +1) because -1 < 1 lexicographically. End events fire before start events at the same t, so a freed room is reused.

Final Expected Approach

Either A or B is acceptable; mention both in the interview.

Data Structures Used

  • Heap approach: the input array (sorted) + a min-heap of end times.
  • Sweep approach: an events array of size 2N + a single integer counter.

Correctness Argument (Heap)

Invariant: after processing intervals 0..i-1 in sorted-by-start order, heap contains the end times of all rooms that are still in use at time intervals[i-1].start. Equivalently, heap is the multiset of end times of meetings that haven’t ended yet by the time we’d schedule the next one.

When processing (s, e):

  • Any heap top ≤ s corresponds to a room whose meeting has ended; it’s reusable. Pop one.
  • Push e for the new meeting.

The final len(heap) is the cumulative maximum number of concurrent meetings, since we only pop when a room frees up (so the heap size strictly decreases only when an old room is reused for a new meeting; otherwise, it grows). Equivalently, max-active-at-any-point = max-rooms-ever-needed.

(Note: we only pop one room even if multiple have ended, but that’s fine — each subsequent meeting will pop its own.)

Correctness Argument (Sweep)

A sweep at time t maintains cur = number of intervals whose start ≤ t < end, half-open. The max of cur over all t is the max concurrency, which is the min rooms needed. The tie-break “end before start at the same time” implements the half-open convention: an end at t decrements cur before a start at t increments it, so cur correctly reflects “intervals active at exactly t” with the half-open semantics.

Complexity

Both: time O(N log N) (sort dominates; heap and sweep each O(N log N) and O(N) respectively after the sort). Space O(N).

Implementation Requirements

  • Sort by start for the heap approach. By start ascending; tie-break doesn’t matter for the heap (because we always pop if heap[0] ≤ s, which is correct for either tie-break).
  • For the sweep approach, the natural tuple sort (time, delta) with delta ∈ {-1, +1} already gives the right tie-break; don’t reverse the comparator.
  • Use a min-heap (Python heapq, Java PriorityQueue default, C++ priority_queue<int, vector<int>, greater<int>>).
  • Don’t sort start-times and end-times separately into two arrays — that’s a third valid approach (the “two pointers” approach, equivalent to sweep) but make sure you understand it’s distinct from the heap approach.

Tests

  • Smoke: the five examples above.
  • Unit: all-disjoint intervals → 1; all-identical intervals → N; chain [1,2],[2,3],[3,4] → 1.
  • Edge: N = 1 → 1; intervals all start at 0 → N (all overlap).
  • Tie-break: [[5,10],[10,15]] → 1 (half-open). If your test returns 2, your sort comparator is wrong.
  • Adversarial: tournament-bracket — [[1,4],[2,5],[7,9],[1,5]] (mix); validate against brute on small inputs.
  • Large: N = 10⁴, random intervals; both heap and sweep should run sub-50ms.

Follow-up Questions

  • “Return the actual schedule (which interval goes in which room)?” → augment heap entries to (end, room_id); reuse the popped room_id for the new interval.
  • “Real-time scheduling: intervals arrive in order, decide room on the fly?” → still works; no offline assumption needed for the heap version (sweep needs all events upfront).
  • “Closed intervals [s, e] instead of half-open?” → flip the tie-break: start before end at the same time, i.e., sort (t, +1) before (t, -1). Or in heap version, change heap[0] <= s to heap[0] < s.
  • “Maximum number of overlapping intervals (LC 1851)?” → identical pattern.
  • “Insert / delete intervals dynamically?” → balanced BST keyed on start; O(log N) per op (Phase 3).
  • “Generalize to weighted intervals?” → DP on intervals (interval scheduling maximization, LC 1235), Phase 3.

Product Extension

Resource allocation in CI/CD: minimum number of build agents required to handle a queue of (start, duration) jobs without delay, given they’re all queued ahead of time. Or: minimum servers needed to handle a known load profile (each request has a known service window). The same heap-of-ends pattern, run on a stream, computes peak concurrency in real time.

Language/Runtime Follow-ups

  • Python: heapq is min-only; for max-heap, negate. heapq.heappop(h) and heapq.heappush(h, x) are O(log N). For sweep, events.sort() on a list of tuples works directly thanks to lexicographic tuple ordering.
  • Java: PriorityQueue<Integer> defaults to min-heap. Boxing tax on primitives — for hot loops, use IntPriorityQueue from a primitive collections lib. Sort intervals via Arrays.sort(intervals, (a, b) -> a[0] - b[0]) — beware overflow (use Integer.compare(a[0], b[0])).
  • Go: container/heap requires implementing the heap.Interface (5 methods). Verbose but flexible.
  • C++: std::priority_queue<int, std::vector<int>, std::greater<int>> for min-heap (default is max). Sort with std::sort.
  • JS/TS: no built-in heap. Implement one (~30 lines) or use a library. For sweep, events.sort((a, b) => a[0] - b[0] || a[1] - b[1]). Beware: Array.sort is not stable in all engines for older versions of V8 (it’s stable since ES2019 — so it’s fine on modern Node, but mention it).
  • Edge: Java’s PriorityQueue.peek() is O(1); poll() is O(log N). C++’s top() is O(1); pop() is O(log N) but doesn’t return the value — call top() first.

Common Bugs

  1. Wrong tie-break in sweep. For half-open intervals, end events must fire before start events at the same time. The natural (time, ±1) tuple sort gives this for free (since -1 < +1); reversing the comparator breaks it.
  2. Heap comparator on max-heap default (Java’s PriorityQueue has a min-heap default; C++’s priority_queue has a max-heap default — easy to forget which is which).
  3. Sorting by end instead of start in the heap approach — gives wrong room counts.
  4. Popping heap on heap[0] < s instead of <= — for half-open [s, e), <= is correct (a meeting ending at s has ended, the room is free for one starting at s).
  5. Forgetting to push the new end after popping — heap loses an entry, undercount.
  6. Comparator overflow in Java: a[0] - b[0] overflows when values are huge; use Integer.compare.
  7. Sweeping events without separating same-time events — fragile; always tie-break explicitly even if the data “happens” to not have ties.

Debugging Strategy

  • Trace [[0,30],[5,10],[15,20]] with the heap approach: sort doesn’t change order. Process [0,30]: heap = [30]. Process [5,10]: 30 > 5, no pop; push 10; heap = [10, 30]. Process [15,20]: 10 ≤ 15, pop; push 20; heap = [20, 30]. Final size = 2. ✓
  • For half-open tie-break: trace [[5,10],[10,15]]. Heap: [10]; second interval, 10 <= 10 → pop, push 15; heap = [15]. Final size 1. ✓ If you used <, you’d get 2.
  • For sweep: events [(5,+1),(10,-1),(10,+1),(15,-1)] sorted: [(5,+1),(10,-1),(10,+1),(15,-1)]. Sweep: cur becomes 1, 0, 1, 0; max 1. ✓
  • Validate against brute on 30 random inputs of size ≤ 50.

Mastery Criteria

  • Recognized “min rooms” / “max concurrent intervals” within 30 seconds.
  • Wrote both heap and sweep solutions within 10 minutes total.
  • Articulated the half-open tie-break before coding.
  • Handled the language-specific heap default (min vs max) without bugs.
  • Identified the connection to LC 1851 (max overlapping intervals) and LC 1094 (Car Pooling).
  • Solved LC 56 (Merge Intervals) and LC 57 (Insert Interval) within a week, observing the same sort-by-start skeleton.