"""
p86 — Meeting Rooms II (LC 253)

INVARIANT (heap): The min-heap of end times equals the set of currently-in-use
  rooms. A new meeting reuses a room iff heap_min <= its start; else allocate.

INVARIANT (sweep): Cumulative sum of +1 (start) / -1 (end) events, sorted by
  (time, kind) with end before start at ties, equals running room count.
"""
from __future__ import annotations

import heapq
import random
from typing import List


def min_meeting_rooms_heap(intervals: List[List[int]]) -> int:
    """Min-heap of end times. O(n log n)."""
    if not intervals:
        return 0
    intervals_sorted = sorted(intervals, key=lambda x: x[0])
    heap: List[int] = []  # end times of in-use rooms
    for start, end in intervals_sorted:
        if heap and heap[0] <= start:
            # Earliest-ending room is free; reuse it.
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)
    return len(heap)


def min_meeting_rooms_sweep(intervals: List[List[int]]) -> int:
    """Sweep line on (+1 start, -1 end) events. O(n log n).
    Ties: ends (-1) processed before starts (+1) to honor [start, end) semantics."""
    if not intervals:
        return 0
    events: List[tuple[int, int]] = []
    for s, e in intervals:
        events.append((s, +1))
        events.append((e, -1))
    # Sorting (time, delta) naturally puts -1 before +1 at same time.
    events.sort()
    cur = 0
    best = 0
    for _, delta in events:
        cur += delta
        if cur > best:
            best = cur
    return best


def min_meeting_rooms_brute(intervals: List[List[int]]) -> int:
    """Oracle: at every distinct start time, count meetings active at that instant.
       Half-open: a meeting [s, e) is active at t iff s <= t < e."""
    if not intervals:
        return 0
    times = sorted({s for s, _ in intervals})
    best = 0
    for t in times:
        cnt = sum(1 for s, e in intervals if s <= t < e)
        if cnt > best:
            best = cnt
    return best


def edge_cases() -> None:
    assert min_meeting_rooms_heap([[0, 30], [5, 10], [15, 20]]) == 2
    assert min_meeting_rooms_sweep([[0, 30], [5, 10], [15, 20]]) == 2

    # Empty.
    assert min_meeting_rooms_heap([]) == 0
    assert min_meeting_rooms_sweep([]) == 0

    # Single.
    assert min_meeting_rooms_heap([[1, 5]]) == 1

    # Touching — half-open, reuses room.
    assert min_meeting_rooms_heap([[1, 5], [5, 10]]) == 1
    assert min_meeting_rooms_sweep([[1, 5], [5, 10]]) == 1

    # All overlapping.
    assert min_meeting_rooms_heap([[1, 10], [2, 10], [3, 10]]) == 3
    assert min_meeting_rooms_sweep([[1, 10], [2, 10], [3, 10]]) == 3

    # Disjoint.
    assert min_meeting_rooms_heap([[1, 2], [3, 4], [5, 6]]) == 1


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(300):
        n = rng.randint(0, 8)
        intervals = []
        for _ in range(n):
            s = rng.randint(0, 10)
            e = rng.randint(s + 1, s + 6)
            intervals.append([s, e])

        heap_ans = min_meeting_rooms_heap([x[:] for x in intervals])
        sweep_ans = min_meeting_rooms_sweep([x[:] for x in intervals])
        brute = min_meeting_rooms_brute([x[:] for x in intervals])
        assert heap_ans == sweep_ans == brute, (intervals, heap_ans, sweep_ans, brute)


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")