5. Maximum Non-Overlapping Eval Harness Runs

Problem

An eval harness has a single GPU worker available for a stretch of time. Multiple candidate eval runs each need an exclusive time window on that worker, and the windows overlap in ways that make it impossible to run all of them.

The scheduler wants to pick the largest possible set of runs that can execute back-to-back on that one worker without any two overlapping.

Source: src/5_max_eval_harness_runs.py

def max_non_overlapping_runs(runs: list[tuple[str, int, int]]) -> list[str]:
    ...

Examples:
>>> max_non_overlapping_runs([("a", 1, 3), ("b", 2, 5), ("c", 4, 6), ("d", 6, 8)])
['a', 'c', 'd']

>>> max_non_overlapping_runs([("x", 1, 2), ("y", 1, 2), ("z", 1, 2)])
['x']

Step-by-Step Approach

1. Recognize this as classic activity selection: maximize the *count* of non-overlapping intervals, not their total duration.
2. Sort all runs by end time ascending (break ties by run_id for determinism) — this is the greedy choice that provably maximizes the count.
3. Walk the sorted runs, keeping track of last_end, the end time of the most recently selected run (initialized to -infinity).
4. For each run in end-time order: if its start is >= last_end, select it and update last_end to its end; otherwise skip it because it would overlap the previous selection.
5. The greedy selection happens in end-time order, but the required output is in start-time order, so re-sort the selected runs by start before returning.

The key insight is that always picking the interval that frees up the resource soonest is provably optimal for maximizing count — a short exchange argument shows any other choice can be swapped for the earliest-finishing one without ever doing worse.

Reference solution

def max_non_overlapping_runs(runs: list[tuple[str, int, int]]) -> list[str]:
    # classic greedy: sort by end time, always take the run that frees the
    # worker soonest. Provably optimal for activity selection, O(n log n).
    sorted_runs = sorted(runs, key=lambda r: (r[2], r[0]))
    selected: list[tuple[str, int]] = []
    last_end = float("-inf")
    for run_id, start, end in sorted_runs:
        if start >= last_end:
            selected.append((run_id, start))
            last_end = end
    # output must be in start-time order, not end-time (selection) order
    selected.sort(key=lambda r: r[1])
    return [run_id for run_id, _ in selected]

Key Functions & Tricks

• sorted(runs, key=lambda r: (r[2], r[0])) — orders by end time first, so the greedy scan always considers the earliest-freeing run next
• last_end tracker — O(1) check for whether the next candidate run overlaps the most recent selection
• start >= last_end — touching endpoints count as non-overlapping, matching the [start, end) convention
• final re-sort by start time — greedy selection order (by end) differs from the required output order (by start)

How to Recognize This Pattern