"""
p89 — Course Schedule III (LC 630)

INVARIANT (Moore-Hodgson swap-out): process courses in deadline order.
  Max-heap of accepted durations. If a new course fits, accept; else if the
  longest accepted is longer than this one, swap (same count, lower cur_time).
"""
from __future__ import annotations

import heapq
import random
from itertools import combinations
from typing import List


def schedule_course_greedy(courses: List[List[int]]) -> int:
    """Moore-Hodgson with max-heap swap-out. O(n log n)."""
    # Sort by deadline ascending.
    courses_sorted = sorted(courses, key=lambda c: c[1])
    heap: List[int] = []  # negated durations of accepted courses
    cur_time = 0
    for d, dl in courses_sorted:
        if cur_time + d <= dl:
            heapq.heappush(heap, -d)
            cur_time += d
        elif heap and -heap[0] > d:
            # Swap out the longest accepted for this one.
            longest = -heap[0]
            heapq.heapreplace(heap, -d)
            cur_time += d - longest  # net decrease
    return len(heap)


def schedule_course_brute(courses: List[List[int]]) -> int:
    """Oracle: try every subset; in deadline order, check feasibility."""
    n = len(courses)
    courses_sorted = sorted(courses, key=lambda c: c[1])
    best = 0
    for size in range(n + 1):
        for subset in combinations(range(n), size):
            cur = 0
            ok = True
            for idx in subset:
                d, dl = courses_sorted[idx]
                if cur + d > dl:
                    ok = False
                    break
                cur += d
            if ok and size > best:
                best = size
    return best


def edge_cases() -> None:
    # LC example.
    assert schedule_course_greedy([[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]) == 3

    # Empty.
    assert schedule_course_greedy([]) == 0

    # All fit.
    assert schedule_course_greedy([[1, 2], [1, 4], [1, 6]]) == 3

    # None fit.
    assert schedule_course_greedy([[5, 1], [10, 2]]) == 0

    # Swap-out case: take 5, then meet 4 with dl=6 (can't fit 5+4=9>6) but
    # swap-out 5 for 4, cur_time=4, then 2 fits (cur_time+2=6 <= 6).
    assert schedule_course_greedy([[5, 5], [4, 6], [2, 6]]) == 2

    # Single course that just fits.
    assert schedule_course_greedy([[5, 5]]) == 1


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(200):
        n = rng.randint(0, 6)
        courses = []
        for _ in range(n):
            d = rng.randint(1, 8)
            dl = rng.randint(d, 12)
            courses.append([d, dl])
        g = schedule_course_greedy([c[:] for c in courses])
        b = schedule_course_brute([c[:] for c in courses])
        assert g == b, (courses, g, b)


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