Sort Events, Then Choose

# festival_dp.py — core TODO 1–8; optional coin challenge TODO 9–10.# An event is (name, start, end, points).# An item is (name, weight, value). Each item may be used ONCE.def insertion_sort_events(events):    """Return a new list sorted by finish time; preserve ties' input order."""    # TODO 1: copy events. For each key, shift later-ending events right.    # Only shift when end > key.end, never when equal.    passdef merge_sort_events(events):    """Return a new, stable finish-time-sorted list in O(n log n)."""    # TODO 2: split, recursively sort both halves, then merge.    # On equal finish times, take from the LEFT half first.    passdef previous_compatible(events):    """For finish-time-sorted events, return p[j] for every j.    p[j] is the last earlier index whose event ends by events[j]'s start.    Return -1 when there is no compatible earlier event.    """    # TODO 3: binary-search only indexes before j. Equality is compatible.    passdef schedule_table(events, previous):    """best[j] is the greatest score using the first j events."""    # TODO 4: best[0] = 0. For each event compare skip and take.    # take = points + best[previous[j] + 1] when j is zero-based.    passdef schedule_plan(events, previous, best):    """Return an optimal compatible list of event names in time order."""    # TODO 5: walk backward through best; jump to p(j) after taking j.    passdef knapsack_table(items, capacity):    """table[i][w] is the greatest value from the first i items in w kg."""    # TODO 6: make (len(items)+1) rows and (capacity+1) columns.    # On taking an item, read from the PREVIOUS row: each item is 0/1.    passdef knapsack_plan(items, capacity, table):    """Recover one optimal list of item names from a completed table."""    # TODO 7: compare table[i][w] with table[i-1][w].    # If item i was taken, reduce w by its weight and move to row i-1.    passdef valid_bag(items, chosen_names, capacity):    """Return True only when a plan uses each item at most once and fits."""    # TODO 8: check names, duplicates, and total weight.    passdef coin_table(amount, coins):    """dp[a] is the fewest coins needed for amount a, for 0 <= a <= amount.    Assume coin 1 exists, so every amount is reachable.    """    # TODO 9: base case dp[0] = 0; try every usable coin for each amount.    passdef coin_plan(amount, coins, dp):    """Recover one minimum-coin plan from a completed table."""    # TODO 10: find a coin c satisfying dp[amount] == 1 + dp[amount-c].    # Append c, reduce amount, repeat until amount is zero.    pass# Checks — keep these below your functions.# Checks: run one stage at a time, for example: python3 festival_dp.py sortimport sysEVENTS = [    ("A", 9.0, 12.0, 100), ("D", 10.5, 11.0, 20),    ("B", 9.5, 10.0, 20), ("E", 11.0, 11.5, 20),    ("C", 10.0, 10.5, 20), ("F", 12.0, 13.0, 50),]ITEMS = [    ("C", 3, 8), ("D", 2, 7), ("E", 5, 13),    ("A", 4, 12), ("B", 3, 9),]def check_coins():    dp = coin_table(6, [1, 3, 4])    assert dp == [0, 1, 2, 1, 1, 2, 2]    assert coin_plan(6, [1, 3, 4], dp) == [3, 3]    print("Coins: 2. Passed.")def check_sort():    original = EVENTS[:]    assert insertion_sort_events([]) == []    assert merge_sort_events([]) == []    ties = [("X", 8, 10, 1), ("Y", 9, 10, 2), ("Z", 8, 9, 3)]    assert [e[0] for e in insertion_sort_events(ties)] == ["Z", "X", "Y"]    assert [e[0] for e in merge_sort_events(ties)] == ["Z", "X", "Y"]    ordered = merge_sort_events(EVENTS)    assert insertion_sort_events(EVENTS) == ordered    assert [e[0] for e in ordered] == ["B", "C", "D", "E", "A", "F"]    assert EVENTS == original    print("Sort: B,C,D,E,A,F. Passed.")def check_schedule():    original = EVENTS[:]    ordered = merge_sort_events(EVENTS)    previous = previous_compatible(ordered)    assert previous == [-1, 0, 1, 2, -1, 4]    best = schedule_table(ordered, previous)    assert best == [0, 20, 40, 60, 80, 100, 150]    assert schedule_plan(ordered, previous, best) == ["A", "F"]    assert EVENTS == original    print("Festival: 150. Passed.")def check_bag():    original = ITEMS[:]    table = knapsack_table(ITEMS, 7)    assert len(table) == len(ITEMS) + 1    assert all(len(row) == 8 for row in table)    assert [row[7] for row in table] == [0, 8, 15, 20, 20, 21]    assert table[-1][7] == 21    assert knapsack_plan(ITEMS, 7, table) == ["A", "B"]    assert table[-1][5] == 16    assert knapsack_plan(ITEMS, 5, table) == ["D", "B"]    assert valid_bag(ITEMS, ["A", "B"], 7)    assert not valid_bag(ITEMS, ["A", "A"], 7)    assert not valid_bag(ITEMS, ["missing"], 7)    assert not valid_bag(ITEMS, ["A", "E"], 7)    assert ITEMS == original    print("Backpack: 7 kg = 21; 5 kg = 16. Passed.")CHECKS = {"sort": check_sort, "schedule": check_schedule,          "bag": check_bag, "coins": check_coins}if __name__ == "__main__":    stage = sys.argv[1] if len(sys.argv) > 1 else "all"    if stage == "all":        for name in ("sort", "schedule", "bag"):            CHECKS[name]()        print("All core checks passed.")    elif stage in CHECKS:        CHECKS[stage]()    else:        print("Choose: sort, schedule, bag, coins, or all.")        sys.exit(2)