25. Schedule GPU Inference Jobs by Deadline

Problem

A shared GPU processes batch inference jobs one at a time, back to back starting at time 0. Each job has a duration and a deadline it must finish by to still be useful (e.g. a nightly fine-tuning eval that's worthless if it lands after the report goes out).

Not every job can make its deadline given everything else competing for the GPU, so pick which subset of jobs to run to maximize the number of jobs that finish by their own deadline. You don't need to say what order to run them in, just which ones make the cut.

Source: src/25_gpu_jobs_by_deadline.py

def max_jobs_by_deadline(jobs: list[tuple[str, int, int]]) -> list[str]: ...

# each job: (job_id, duration, deadline)

>>> max_jobs_by_deadline([("a", 3, 5), ("b", 2, 5), ("c", 4, 5)])
['a', 'b']
>>> max_jobs_by_deadline([("only", 10, 3)])
[]

Step-by-Step Approach

1. Sort jobs by deadline ascending — process the most time-pressured jobs first, since a job with an earlier deadline has strictly less room for error.
2. Walk the sorted jobs, tentatively accepting every one: push its duration onto a max-heap of accepted durations (via negation, since Python's heapq is a min-heap) and add it to a running total time.
3. After tentatively accepting a job, check whether the running total now exceeds that job's own deadline — since jobs are processed in deadline order, this is the earliest point such a violation could occur for the jobs accepted so far.
4. If it does exceed, evict the single longest-duration job accepted so far (the top of the max-heap) rather than the current job specifically — this frees the most slack for the fewest jobs given up.
5. Continue through all jobs; whatever remains on the heap at the end is a maximum-size feasible subset. Sort the surviving job ids for a deterministic return value.

The key insight is the exchange argument behind the greedy: among any set of already-accepted jobs that together violate a deadline, evicting the longest one is always at least as good as evicting any other, because it removes the most total time from the schedule while only costing exactly one job slot — so the heap-based "accept greedily, evict the worst offender" strategy never does worse than any other choice of what to give up.

Reference solution

import heapq


def max_jobs_by_deadline(jobs: list[tuple[str, int, int]]) -> list[str]:
    # Classic deadline-constrained scheduling greedy: process jobs in
    # deadline order, tentatively accept every one, and keep a max-heap
    # (via negated durations) of the accepted jobs' durations. Whenever the
    # running total exceeds the current job's deadline, evict the single
    # LONGEST job accepted so far -- swapping out the biggest time-sink is
    # always at least as good as swapping out any other accepted job,
    # because it frees the most slack while only costing one job slot.
    jobs_sorted = sorted(jobs, key=lambda j: (j[2], j[0]))  # by deadline, then id for determinism
    heap: list[tuple[int, str]] = []  # (-duration, job_id) -- min-heap acting as max-heap on duration
    total = 0
    for job_id, duration, deadline in jobs_sorted:
        heapq.heappush(heap, (-duration, job_id))
        total += duration
        if total > deadline:
            worst_neg_duration, _worst_id = heapq.heappop(heap)
            total += worst_neg_duration  # adding a negative duration subtracts it
    return sorted(job_id for _, job_id in heap)

Key Functions & Tricks

• Sorting by (deadline, job_id) — processes the most time-constrained jobs first, which is what makes the greedy's exchange argument valid.
• Negated-duration min-heap — the standard Python idiom for a max-heap, here tracking the single most "expensive" accepted job.
• total += worst_neg_duration — adding a negative value is the same as subtracting the evicted job's positive duration.
• Evicting the longest job rather than the current one — the crux of the greedy; evicting the current job instead is a common but suboptimal simplification.

How to Recognize This Pattern