"""
p84 — Minimum Number of Arrows to Burst Balloons (LC 452)

INVARIANT: After sorting by end, the optimal greedy stabs at the smallest end
  among uncovered intervals. Any interval starting <= current arrow is covered.

Equivalent: min arrows == max disjoint intervals.
"""
from __future__ import annotations

import random
from itertools import combinations
from typing import List


def find_min_arrow_shots(points: List[List[int]]) -> int:
    """O(n log n) sort by end + sweep."""
    if not points:
        return 0
    pts = sorted(points, key=lambda p: p[1])
    arrows = 1
    arrow = pts[0][1]
    for start, end in pts[1:]:
        if start > arrow:
            # Current arrow doesn't cover this balloon; need a new one.
            arrows += 1
            arrow = end
    return arrows


def find_min_arrow_shots_brute(points: List[List[int]]) -> int:
    """Oracle: try all subsets of candidate arrow positions (interval endpoints).
       For small inputs only — 2^(2n) subsets."""
    if not points:
        return 0
    # Candidate positions: every endpoint.
    candidates = sorted({p[0] for p in points} | {p[1] for p in points})

    def covers_all(arrow_set: List[int]) -> bool:
        for s, e in points:
            if not any(s <= a <= e for a in arrow_set):
                return False
        return True

    for size in range(1, len(points) + 1):
        for combo in combinations(candidates, size):
            if covers_all(list(combo)):
                return size
    return len(points)


def edge_cases() -> None:
    assert find_min_arrow_shots([[10, 16], [2, 8], [1, 6], [7, 12]]) == 2
    assert find_min_arrow_shots([[1, 2], [3, 4], [5, 6], [7, 8]]) == 4  # all disjoint
    assert find_min_arrow_shots([[1, 2], [2, 3], [3, 4], [4, 5]]) == 2  # chain w/ touching
    assert find_min_arrow_shots([]) == 0
    assert find_min_arrow_shots([[1, 1]]) == 1
    # All share a common point.
    assert find_min_arrow_shots([[1, 10], [2, 9], [3, 8], [4, 7]]) == 1


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(200):
        n = rng.randint(0, 5)
        points = []
        for _ in range(n):
            a = rng.randint(0, 8)
            b = rng.randint(a, 10)
            points.append([a, b])

        got = find_min_arrow_shots([p[:] for p in points])
        brute = find_min_arrow_shots_brute([p[:] for p in points])
        assert got == brute, (points, got, brute)


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