"""
Merge overlapping, prioritised time ranges into one track.

Each record is (start, end, priority). The priority is a unique integer that
also identifies the track. Ranges are half-open: [start, end). At every moment
the track with the highest priority among those currently playing wins.
Several records may share a priority (the same track playing more than once).

    >>> recs = [Record(0, 10, 1), Record(3, 6, 5), Record(5, 8, 3)]
    >>> merge(recs)
    [Segment(start=0, end=3, track=1), Segment(start=3, end=6, track=5), \
Segment(start=6, end=8, track=3), Segment(start=8, end=10, track=1)]
    >>> [(s.at, s.from_track, s.to_track, s.reason) for s in switches(merge(recs))]
    [(0, None, 1, 'start'), (3, 1, 5, 'preempt'), (6, 5, 3, 'fallback'), (8, 3, 1, 'resume'), (10, 1, None, 'end')]

Algorithm (sweep line + max-heap with lazy deletion), O(n log n):

1. Turn every record into two events: +1 at start, -1 at end.
2. Sort events by time and walk them, one distinct time at a time.
3. Keep `active[track]` = how many records of that track are playing, and a
   heap of tracks. Ending a record only decrements the counter; dead tracks are
   popped off the heap lazily, when they reach the top.
4. After applying all events at time t, the heap top is the winner from t on.
   If it differs from the previous winner, close the open segment at t and
   open a new one. That moment is a switch.
"""

from __future__ import annotations

import heapq
from collections import defaultdict
from dataclasses import dataclass
from itertools import groupby
from typing import Iterable, Literal, Optional

Number = float | int


@dataclass(frozen=True)
class Record:
    start: Number
    end: Number
    priority: int  # unique per track; also the track id


@dataclass(frozen=True)
class Segment:
    start: Number
    end: Number
    track: int


@dataclass(frozen=True)
class Switch:
    at: Number
    from_track: Optional[int]  # None = silence before
    to_track: Optional[int]    # None = silence after
    reason: Literal["start", "preempt", "fallback", "resume", "end"]


def merge(records: Iterable[Record], higher_wins: bool = True) -> list[Segment]:
    """Return the merged single track as non-overlapping segments, in time order.

    Gaps where nothing plays are simply absent from the result.
    Set higher_wins=False if a smaller number means a more important track.
    """
    sign = -1 if higher_wins else 1  # heapq is a min-heap

    events: list[tuple[Number, int, int]] = []  # (time, delta, track)
    for r in records:
        if r.end < r.start:
            raise ValueError(f"end before start: {r}")
        if r.end == r.start:
            continue  # zero-length, never audible
        events.append((r.start, +1, r.priority))
        events.append((r.end, -1, r.priority))
    events.sort(key=lambda e: e[0])

    active: dict[int, int] = defaultdict(int)
    heap: list[int] = []  # sign * track
    out: list[Segment] = []
    current: Optional[int] = None
    opened_at: Number = 0

    for t, group in groupby(events, key=lambda e: e[0]):
        for _, delta, track in group:
            active[track] += delta
            if delta > 0 and active[track] == 1:
                heapq.heappush(heap, sign * track)

        while heap and active[sign * heap[0]] == 0:  # lazy deletion
            heapq.heappop(heap)
        winner = sign * heap[0] if heap else None

        if winner != current:
            if current is not None and t > opened_at:
                out.append(Segment(opened_at, t, current))
            current, opened_at = winner, t

    return out


def switches(segments: list[Segment], higher_wins: bool = True) -> list[Switch]:
    """Every moment the output changes track, including silence at either side.

    Pass the same higher_wins you gave merge().

    reason:
      start     - playback begins after silence (or at the very beginning)
      preempt   - a more important track interrupted the one playing
      fallback  - the playing track ended; a less important one takes over
      resume    - like fallback, but the track taking over already played
                  earlier, i.e. it was interrupted and now continues
      end       - nothing plays anymore (a gap, or the very end)
    """
    out: list[Switch] = []
    seen: set[int] = set()
    prev: Optional[Segment] = None
    for seg in segments:
        if prev is None or prev.end < seg.start:  # silence before this segment
            if prev is not None:
                out.append(Switch(prev.end, prev.track, None, "end"))
            out.append(Switch(seg.start, None, seg.track, "start"))
        elif (seg.track > prev.track) == higher_wins:
            # Only a more important track can take over a still-playing one.
            out.append(Switch(seg.start, prev.track, seg.track, "preempt"))
        else:
            # A less important track only wins once the playing one has ended.
            reason = "resume" if seg.track in seen else "fallback"
            out.append(Switch(seg.start, prev.track, seg.track, reason))
        seen.add(seg.track)
        prev = seg
    if prev is not None:
        out.append(Switch(prev.end, prev.track, None, "end"))
    return out


def airtime(segments: list[Segment]) -> dict[int, Number]:
    """Total seconds each track is audible in the merged output."""
    total: dict[int, Number] = defaultdict(int)
    for s in segments:
        total[s.track] += s.end - s.start
    return dict(total)


if __name__ == "__main__":
    records = [
        Record(0, 20, 1),   # background, lowest
        Record(4, 12, 3),
        Record(6, 9, 7),    # highest, interrupts 3
        Record(10, 15, 5),  # interrupts 3, keeps playing after it ends
        Record(14, 16, 7),  # track 7 again
        Record(22, 25, 2),  # after a gap
    ]
    segs = merge(records)
    print("Merged track:")
    for s in segs:
        print(f"  {s.start:>5} – {s.end:<5} track {s.track}")
    print("\nSwitches:")
    for w in switches(segs):
        f = "—" if w.from_track is None else w.from_track
        t = "—" if w.to_track is None else w.to_track
        print(f"  t={w.at:<5} {f} → {t}   ({w.reason})")
    print("\nAirtime:", airtime(segs))