"""Interval overlap/merge utilities with well-defined boundary semantics.

Boundary convention: intervals are half-open [start, end). Two intervals
overlap iff they share at least one point, i.e. max(s1,s2) < min(e1,e2).
Touching at a point (e.g. [1,2) and [2,3)) does NOT overlap and is NOT
merged (they remain distinct). This matches the common scheduling convention.
"""
from __future__ import annotations

from typing import Iterable, List, Tuple

Interval = Tuple[int, int]


def _validate(iv: Interval) -> None:
    if not (isinstance(iv, tuple) and len(iv) == 2):
        raise ValueError(f"interval must be 2-tuple, got {iv!r}")
    s, e = iv
    if not (isinstance(s, int) and isinstance(e, int)):
        raise ValueError(f"endpoints must be int, got {iv!r}")
    if s > e:
        raise ValueError(f"start > end in {iv!r}")


def normalize(intervals: Iterable[Interval]) -> List[Interval]:
    """Validate, drop empties, return sorted by (start, end)."""
    out: List[Interval] = []
    for iv in intervals:
        _validate(iv)
        s, e = iv
        if s == e:
            continue  # empty interval contributes nothing
        out.append((s, e))
    out.sort(key=lambda x: (x[0], x[1]))
    return out


def overlaps(a: Interval, b: Interval) -> bool:
    _validate(a); _validate(b)
    return max(a[0], b[0]) < min(a[1], b[1])


def merge(intervals: Iterable[Interval]) -> List[Interval]:
    """Merge overlapping intervals (half-open). Touching intervals stay separate."""
    ivs = normalize(intervals)
    if not ivs:
        return []
    merged: List[Interval] = [ivs[0]]
    for s, e in ivs[1:]:
        ls, le = merged[-1]
        if s < le:  # strict: touching (s == le) does not merge
            merged[-1] = (ls, max(le, e))
        else:
            merged.append((s, e))
    return merged


def total_covered(intervals: Iterable[Interval]) -> int:
    """Total length of union of intervals (half-open length = end - start)."""
    return sum(e - s for s, e in merge(intervals))


def find_gaps(intervals: Iterable[Interval], lo: int, hi: int) -> List[Interval]:
    """Gaps within [lo, hi) not covered by any interval."""
    if lo > hi:
        raise ValueError("lo > hi")
    merged = merge(intervals)
    gaps: List[Interval] = []
    cur = lo
    for s, e in merged:
        if e <= cur or s >= hi:
            continue
        ss = max(s, lo)
        ee = min(e, hi)
        if ss > cur:
            gaps.append((cur, ss))
        cur = max(cur, ee)
        if cur >= hi:
            break
    if cur < hi:
        gaps.append((cur, hi))
    return gaps