会议越早结束就先选？场次最多和收入最高是两道题

"""Maximum count is not maximum revenue in interval scheduling."""
from itertools import combinations
import json


def validate(jobs):
    jobs = tuple(jobs)
    if len(jobs) > 1000:
        raise ValueError("teaching limit: 1000 jobs")
    for start, end, value in jobs:
        if any(type(x) is not int for x in (start, end, value)) or start >= end or value < 0:
            raise ValueError("integer start < end and nonnegative integer value required")
    return jobs


def earliest_finish(jobs):
    jobs = validate(jobs)
    chosen, end = [], None
    for i in sorted(range(len(jobs)), key=lambda i: (jobs[i][1], jobs[i][0], i)):
        if end is None or jobs[i][0] >= end:
            chosen.append(i)
            end = jobs[i][1]
    return chosen


def maximum_value(jobs):
    jobs = validate(jobs)
    order = sorted(range(len(jobs)), key=lambda i: (jobs[i][1], jobs[i][0], i))
    best, plans = [0], [()]
    for j, i in enumerate(order):
        # Deliberately use a visible linear scan; this version is O(n^2).
        p = j - 1
        while p >= 0 and jobs[order[p]][1] > jobs[i][0]:
            p -= 1
        take = jobs[i][2] + best[p + 1]
        if take > best[-1]:
            best.append(take)
            plans.append(plans[p + 1] + (i,))
        else:
            best.append(best[-1])
            plans.append(plans[-1])
    return best[-1], list(plans[-1])


def exhaustive(jobs):
    # Independent oracle: all subsets, all pairs; no finish-order recurrence.
    if len(jobs) > 12:
        raise ValueError("oracle limited to twelve jobs")
    best_count, best_value = 0, 0
    for mask in range(1 << len(jobs)):
        chosen = [i for i in range(len(jobs)) if mask >> i & 1]
        if all(jobs[a][1] <= jobs[b][0] or jobs[b][1] <= jobs[a][0]
               for a, b in combinations(chosen, 2)):
            best_count = max(best_count, len(chosen))
            best_value = max(best_value, sum(jobs[i][2] for i in chosen))
    return best_count, best_value


def main():
    checks = 0
    def check(ok):
        nonlocal checks
        if not ok:
            raise AssertionError("interval check failed")
        checks += 1
    pool = [(a, b, (a * 3 + b) % 7) for a, b in combinations(range(5), 2)]
    cases = 0
    for mask in range(1 << len(pool)):
        jobs = [j for i, j in enumerate(pool) if mask >> i & 1]
        count, value = exhaustive(jobs)
        chosen = earliest_finish(jobs)
        dp_value, dp_plan = maximum_value(jobs)
        check(len(chosen) == count)
        check(dp_value == value)
        check(sum(jobs[i][2] for i in dp_plan) == dp_value)
        check(all(jobs[a][1] <= jobs[b][0] for a, b in zip(dp_plan, dp_plan[1:])))
        cases += 1
    demo = [(0, 2, 1), (2, 4, 1), (0, 4, 10)]
    chosen = earliest_finish(demo)
    check(chosen == [0, 1])
    check(maximum_value(demo) == (10, [2]))
    check(earliest_finish(iter(demo)) == chosen)
    check(len(earliest_finish([(-3, -1, 2), (-1, 0, 2)])) == 2)
    check(exhaustive([(0, 2, 1), (0, 2, 3)]) == (1, 3))
    for jobs in [[(1, 1, 1)], [(2, 1, 1)], [(0, 1, -1)], [(0, True, 1)]]:
        try:
            earliest_finish(jobs)
        except ValueError:
            check(True)
        else:
            raise AssertionError("invalid interval accepted")
    print(json.dumps({"checks_passed": checks, "exhaustive_job_sets": cases,
                      "jobs_start_end_value": demo, "maximum_count_plan": chosen,
                      "count_plan_value": sum(demo[i][2] for i in chosen),
                      "maximum_value_result": maximum_value(demo),
                      "scope": "one room; fixed half-open intervals [start,end); adjacency allowed; offline"}, indent=2))


if __name__ == "__main__":
    main()