37. Min GPU Workers to Cover a Job Schedule

Problem

A cluster scheduler has a fixed list of training jobs, each with a known [start_step, end_step) window during which it needs a dedicated GPU worker. Two jobs whose windows overlap cannot share a worker.

Before provisioning the cluster, the scheduler needs to know the minimum number of GPU workers required so every job gets one, without ever double-booking a worker. This must run in O(n log n) time via a sweep over sorted start/end events, not by checking every pair of jobs.

Source: src/37_min_gpu_workers_job_schedule.py

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

Examples:
>>> min_gpu_workers([(0, 5), (1, 3), (4, 8)])
2

>>> min_gpu_workers([(0, 2), (2, 4)])
1

Step-by-Step Approach

1. Reframe "minimum workers" as "maximum number of jobs simultaneously in progress at any instant" — that peak concurrency is exactly the number of workers you need.
2. Instead of tracking a timeline, split each job into two independent events: a start and an end. Sort all starts and all ends separately.
3. Walk both sorted lists with two pointers. At each step, compare the next unprocessed start to the next unprocessed end.
4. If the next start happens before the next end, a new job has begun while an old one is still running: increment the concurrency counter and record a new peak if it's higher than any seen so far.
5. Otherwise, a job has ended before (or exactly when) the next one starts: decrement the concurrency counter to free up that worker before considering the next start.
6. Because jobs use half-open [start, end) windows, a job ending exactly when another starts does not count as an overlap — that's why ties between a start and an end favor processing the end first.

The key insight is that you never need to know which specific job occupies which worker — only the peak count of jobs alive at the same instant, which the sorted start/end sweep gives you directly without simulating a timeline.

Reference solution

def min_gpu_workers(jobs: list[tuple[int, int]]) -> int:
    if not jobs:
        return 0
    # sort starts and ends independently -- classic "meeting rooms II" sweep, O(n log n)
    starts = sorted(start for start, _ in jobs)
    ends = sorted(end for _, end in jobs)
    i = j = 0
    current = peak = 0
    n = len(jobs)
    while i < n:
        if starts[i] < ends[j]:
            # a job starts before the earliest still-running job ends -> need another worker
            current += 1
            peak = max(peak, current)
            i += 1
        else:
            # earliest running job has ended -> free up a worker before considering the next start
            current -= 1
            j += 1
    return peak

Key Functions & Tricks

• sorted(start for start, _ in jobs) — decouples starts from ends, letting each be swept independently
• Two-pointer event sweep — walks starts and ends in tandem instead of building an explicit timeline array
• starts[i] < ends[j] tie rule — a job ending exactly when another starts is not treated as overlap, matching half-open interval semantics
• Peak concurrency tracking — the answer is the maximum value the running counter ever reaches, not its final value
• Equivalent min-heap formulation — sort jobs by start, push each end time onto a heap, and pop expired ends before each new push; same O(n log n) bound, useful when jobs must also be assigned to specific worker IDs

How to Recognize This Pattern