15. Priority Queue for Inference Job Scheduling

Problem

A lab runs one GPU-backed inference server that processes jobs one at a time. Jobs arrive at different times and carry different priority tiers (e.g. an interactive chat completion should preempt a queued batch summarization job). Whenever the server frees up, it must pick, among jobs that have already arrived and are still waiting, the one with the highest priority (lowest priority number); ties go to whichever arrived earliest, then to job ID for determinism. If nothing has arrived yet, the server sits idle until the next job arrives.

Simulate this scheduler and return the job IDs in the order the server processes them. Each job takes exactly 1 tick to process, and a job already running is never preempted mid-run — only the choice of which waiting job to start next is priority-based.

Source: src/15_priority_inference_job_scheduler.py

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

>>> inference_job_order([("a", 0, 2), ("b", 0, 1), ("c", 1, 0)])
['b', 'c', 'a']
>>> inference_job_order([("j1", 0, 5), ("j2", 1, 1), ("j3", 2, 1)])
['j1', 'j2', 'j3']

Step-by-Step Approach

1. Separate the problem into two concerns: which jobs exist but haven't arrived yet (ordered by arrival time), and which jobs have arrived and are waiting for the server (ordered by priority). Two heaps, one per concern.
2. Sort all jobs by (arrival_time, priority, job_id) once up front into a pending list, and walk it with a pointer instead of re-scanning it — this is the "not yet arrived" heap, cheaply represented as a sorted list plus an index.
3. Maintain a ready min-heap keyed by (priority, arrival_time, job_id) for jobs that have arrived but not yet run.
4. At each step, if ready is empty, fast-forward the clock to the next pending job's arrival time — the server can't do anything before then.
5. Release every pending job whose arrival time is <= clock into the ready heap (there may be several arriving at the same tick).
6. Pop the best (lowest priority number, earliest arrival, smallest job ID) job from ready, append it to the output, and advance the clock by 1 tick (its processing time).
7. Repeat until both pending and ready are empty.

The key insight is that "release jobs as they arrive, then pick greedily by priority among what's currently available" is exactly what the two-heap structure encodes: the pending heap answers "what's not available yet" and the ready heap answers "of what's available, what's best" — conflating them into one heap would let a low-priority job that arrived early get picked over a high-priority job that just hasn't arrived, or vice versa, silently wrong.

Reference solution

import heapq


def inference_job_order(jobs: list[tuple[str, int, int]]) -> list[str]:
    # two heaps: `pending` holds jobs not yet arrived (ordered by arrival
    # time), `ready` holds arrived-but-unprocessed jobs (ordered by
    # priority). O(n log n) total.
    pending = sorted(jobs, key=lambda j: (j[1], j[2], j[0]))
    ptr = 0
    n = len(pending)
    ready: list[tuple[int, int, str]] = []  # (priority, arrival_time, job_id)
    clock = 0
    order: list[str] = []

    while ptr < n or ready:
        if not ready:
            # server is idle -- fast-forward the clock to the next arrival
            clock = max(clock, pending[ptr][1])
        # release every job that has arrived by "now" into the ready heap
        while ptr < n and pending[ptr][1] <= clock:
            job_id, arrival_time, priority = pending[ptr]
            heapq.heappush(ready, (priority, arrival_time, job_id))
            ptr += 1
        priority, arrival_time, job_id = heapq.heappop(ready)
        order.append(job_id)
        clock += 1  # this job occupies the server for exactly one tick

    return order

Key Functions & Tricks

• sorted(jobs, key=(arrival, priority, id)) — precomputes the arrival order once, turning "what's not arrived yet" into a simple pointer walk instead of a second heap.
• heapq.heappush / heapq.heappop on ready — always surfaces the best currently-available job in O(log n).
• (priority, arrival_time, job_id) tuple key — encodes the full tie-break chain (priority, then arrival, then ID) directly in heap comparison order.
• clock = max(clock, pending[ptr][1]) — models the server idling forward in time when nothing is ready yet, instead of ticking one unit at a time.
• while ptr < n and pending[ptr][1] <= clock — releases every job that has arrived by "now," not just the next one, correctly handling simultaneous arrivals.

How to Recognize This Pattern