"""
p49 — Meeting Rooms II (LeetCode 253, MEDIUM).

Half-open semantics: meeting [a, b] frees the room at time b; another meeting
starting at b doesn't conflict.

Implementations:
    min_meeting_rooms_heap          — sort + min-heap of end times. O(n log n).
    min_meeting_rooms_two_pointer   — sort starts/ends independently, sweep. O(n log n).
    min_meeting_rooms_sweep_line    — (time, ±1) events. O(n log n).
    min_meeting_rooms_brute         — minute-by-minute active count. O(T * n).

Stress: 1000 random; all four agree.
"""
from __future__ import annotations
import heapq
import random
from typing import List


# --------------------------------------------------------------------------------------
# Heap of end times. O(n log n).
# INVARIANT: heap contains end-times of rooms CURRENTLY IN USE.
# For each new meeting (in start order): pop one room whose end <= start (it freed up).
# Push current end. Track max heap size after each push.
# --------------------------------------------------------------------------------------
def min_meeting_rooms_heap(intervals: List[List[int]]) -> int:
    if not intervals:
        return 0
    arr = sorted(intervals, key=lambda x: x[0])
    heap: List[int] = []
    peak = 0
    for s, e in arr:
        if heap and heap[0] <= s:   # half-open: == means free
            heapq.heappop(heap)
        heapq.heappush(heap, e)
        peak = max(peak, len(heap))
    return peak


# --------------------------------------------------------------------------------------
# Two-pointer over independently-sorted starts and ends. O(n log n).
# At each "start before end" event: a new room is needed. Else a room frees up.
# --------------------------------------------------------------------------------------
def min_meeting_rooms_two_pointer(intervals: List[List[int]]) -> int:
    if not intervals:
        return 0
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)
    n = len(intervals)
    s = e = active = peak = 0
    while s < n:
        if starts[s] < ends[e]:    # half-open: new starts strictly before old ends
            active += 1
            peak = max(peak, active)
            s += 1
        else:                       # ends[e] <= starts[s]: room freed
            active -= 1
            e += 1
    return peak


# --------------------------------------------------------------------------------------
# Sweep-line with (time, delta) events. O(n log n).
# Half-open: process -1 BEFORE +1 at the same time (sort key: (time, delta)).
# --------------------------------------------------------------------------------------
def min_meeting_rooms_sweep_line(intervals: List[List[int]]) -> int:
    events: List[tuple] = []
    for s, e in intervals:
        events.append((s, 1))
        events.append((e, -1))
    events.sort(key=lambda x: (x[0], x[1]))   # -1 before +1 at same time
    peak = active = 0
    for _, delta in events:
        active += delta
        peak = max(peak, active)
    return peak


# --------------------------------------------------------------------------------------
# Brute oracle: count active rooms at each minute in [min_start, max_end - 1].
# Half-open: a meeting [a, b] is active at time t iff a <= t < b.
# --------------------------------------------------------------------------------------
def min_meeting_rooms_brute(intervals: List[List[int]]) -> int:
    if not intervals:
        return 0
    lo = min(s for s, _ in intervals)
    hi = max(e for _, e in intervals)
    peak = 0
    for t in range(lo, hi):
        active = sum(1 for s, e in intervals if s <= t < e)
        peak = max(peak, active)
    return peak


# --------------------------------------------------------------------------------------
# Tests
# --------------------------------------------------------------------------------------
def edge_cases() -> None:
    assert min_meeting_rooms_heap([[0, 30], [5, 10], [15, 20]]) == 2
    assert min_meeting_rooms_heap([[7, 10], [2, 4]]) == 1
    assert min_meeting_rooms_heap([[0, 10], [10, 20]]) == 1     # half-open touch
    assert min_meeting_rooms_heap([]) == 0
    assert min_meeting_rooms_heap([[1, 5]]) == 1
    assert min_meeting_rooms_heap([[1, 5], [2, 6], [3, 7], [4, 8]]) == 4

    # All variants agree
    for fn in (min_meeting_rooms_two_pointer, min_meeting_rooms_sweep_line, min_meeting_rooms_brute):
        assert fn([[0, 30], [5, 10], [15, 20]]) == 2
        assert fn([[0, 10], [10, 20]]) == 1
        assert fn([[1, 5], [2, 6], [3, 7], [4, 8]]) == 4
        assert fn([]) == 0

    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(1000):
        n = rng.randint(0, 12)
        intervals = []
        for _ in range(n):
            a = rng.randint(0, 15)
            b = rng.randint(a + 1, a + 8)
            intervals.append([a, b])

        r1 = min_meeting_rooms_heap([list(x) for x in intervals])
        r2 = min_meeting_rooms_two_pointer([list(x) for x in intervals])
        r3 = min_meeting_rooms_sweep_line([list(x) for x in intervals])
        r4 = min_meeting_rooms_brute([list(x) for x in intervals])

        assert r1 == r2 == r3 == r4, (
            f"trial {trial}: heap={r1} 2p={r2} sweep={r3} brute={r4} input={intervals}"
        )

    print("stress_test: 1000 random trials — heap, two-pointer, sweep-line, brute all agree.")


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