"""
p46 — Merge Intervals (LeetCode 56, MEDIUM).

Three implementations:
    merge_intervals             — sort + sweep. O(n log n). Canonical.
    merge_intervals_sweep_line  — (point, ±1) events. O(n log n). Alternative.
    merge_intervals_brute       — repeated pair-merge oracle. O(n^3). Tiny inputs.

Closed-interval semantics per LC 56: [1, 2] and [2, 3] DO merge.

Stress: 1000 random inputs; all three agree.
"""
from __future__ import annotations
import random
from typing import List


# --------------------------------------------------------------------------------------
# Canonical: sort + sweep. O(n log n).
# INVARIANT: out is a list of disjoint intervals sorted by start; after sorting input
# by start, the ONLY interval in out that can overlap current is out[-1].
# --------------------------------------------------------------------------------------
def merge_intervals(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return []
    arr = sorted(intervals, key=lambda x: x[0])
    out: List[List[int]] = [list(arr[0])]   # fresh copies — avoid input aliasing
    for s, e in arr[1:]:
        if s <= out[-1][1]:                 # closed-interval overlap
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out


# --------------------------------------------------------------------------------------
# Sweep-line with (point, delta) events. O(n log n).
# Tie-break: +1 before -1 for closed intervals (so touching counts as overlap).
# Active count > 0 => inside a merged interval.
# --------------------------------------------------------------------------------------
def merge_intervals_sweep_line(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return []
    # (point, type) where type=0 for start (process first), type=1 for end (process after).
    events: List[tuple] = []
    for s, e in intervals:
        events.append((s, 0))
        events.append((e, 1))
    events.sort()   # by point asc; type asc means start before end at same point (closed merge)

    out: List[List[int]] = []
    active = 0
    cur_start = 0
    for point, typ in events:
        if typ == 0:
            if active == 0:
                cur_start = point
            active += 1
        else:
            active -= 1
            if active == 0:
                out.append([cur_start, point])
    return out


# --------------------------------------------------------------------------------------
# Brute oracle: keep merging any overlapping pair until stable. O(n^3) ish.
# --------------------------------------------------------------------------------------
def merge_intervals_brute(intervals: List[List[int]]) -> List[List[int]]:
    arr = [list(x) for x in intervals]
    changed = True
    while changed:
        changed = False
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                a, b = arr[i], arr[j]
                if max(a[0], b[0]) <= min(a[1], b[1]):   # overlap (closed)
                    arr[i] = [min(a[0], b[0]), max(a[1], b[1])]
                    arr.pop(j)
                    changed = True
                    break
            if changed:
                break
    arr.sort(key=lambda x: x[0])
    return arr


# --------------------------------------------------------------------------------------
# Tests
# --------------------------------------------------------------------------------------
def edge_cases() -> None:
    # LC canonical
    assert merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]) == [[1, 6], [8, 10], [15, 18]]
    # Touching (closed merge)
    assert merge_intervals([[1, 4], [4, 5]]) == [[1, 5]]
    # Contained
    assert merge_intervals([[1, 10], [2, 3], [4, 5]]) == [[1, 10]]
    # Single
    assert merge_intervals([[1, 1]]) == [[1, 1]]
    # Empty
    assert merge_intervals([]) == []
    # All disjoint
    assert merge_intervals([[5, 6], [1, 2], [3, 4]]) == [[1, 2], [3, 4], [5, 6]]
    # All same
    assert merge_intervals([[1, 5], [1, 5], [1, 5]]) == [[1, 5]]
    # Reverse-sorted input
    assert merge_intervals([[8, 10], [1, 3], [2, 6]]) == [[1, 6], [8, 10]]

    # Sweep-line variant agreement
    assert merge_intervals_sweep_line([[1, 3], [2, 6], [8, 10]]) == [[1, 6], [8, 10]]
    assert merge_intervals_sweep_line([[1, 4], [4, 5]]) == [[1, 5]]
    assert merge_intervals_sweep_line([]) == []

    print("edge_cases: PASS")


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

        a = merge_intervals(intervals)
        b = merge_intervals_sweep_line(intervals)
        c = merge_intervals_brute(intervals)

        assert a == b == c, f"trial {trial}: a={a} b={b} c={c} input={intervals}"

    print("stress_test: 1000 random trials — sort+sweep, sweep-line, brute all agree.")


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