43. Schedule Inference Jobs with GPU Cooldown

Problem

A shared GPU inference slot serves requests for several model types — say, distinct Sonic voice variants or Ink-2 model configs. Exactly one job runs per time unit, but after a job of a given model type finishes, that same model type must sit idle for cooldown time units before it can run again, so the GPU has time to reset per-model state between runs.

The scheduler receives a batch of queued jobs, given as model-type labels, and may reorder them however it likes to finish as fast as possible. Idle slots (no job runs) count toward the total. Return the minimum number of time units needed to run every job while respecting the cooldown between same-type jobs.

Source: src/43_schedule_inference_jobs_cooldown.py

def min_schedule_time(jobs: list[str], cooldown: int) -> int:

>>> min_schedule_time(["A", "A", "A", "B", "B", "B"], 2)
8

>>> min_schedule_time(["A", "A", "A", "B", "B", "B"], 0)
6

Step-by-Step Approach

1. Notice the schedule's minimum length is driven entirely by whichever model type(s) appear most often — every other job type is flexible padding that can slot into the gaps those leave behind.
2. Count how often each model type appears. Let max_freq be the highest count and count_max be how many types are tied at that count.
3. The most frequent type needs max_freq - 1 full cooldown gaps between its own occurrences, each gap being cooldown + 1 slots wide (the run itself plus the cooldown).
4. In the very last of those gaps, every other type tied for max_freq also needs one slot for its final occurrence, so add count_max to the frame.
5. That gives a lower bound: frame = (max_freq - 1) * (cooldown + 1) + count_max. If there are enough distinct job types to fill every idle slot in that frame, no idle time is actually needed — the real answer is just len(jobs).
6. The answer is therefore max(frame, len(jobs)): idle time only appears when the most-frequent type(s) can't be fully padded out by the rest of the batch.
7. Handle the trivial cases: an empty batch takes 0 time, and cooldown = 0 means no gaps are needed at all, so the answer collapses to len(jobs).

The key insight is that you never need to construct the actual schedule — the answer is a closed-form counting formula derived from the single most constrained job type, taking the max against the total job count to catch the case where there's enough variety to pack every gap.

Reference solution

from collections import Counter


def min_schedule_time(jobs: list[str], cooldown: int) -> int:
    if not jobs:
        return 0
    # count how often each model type appears in the batch
    counts = Counter(jobs)
    max_freq = max(counts.values())
    # how many model types are tied for the highest frequency
    count_max = sum(1 for freq in counts.values() if freq == max_freq)
    # the most frequent type(s) pin the minimum length: (max_freq - 1) full
    # cooldown gaps, plus one slot for each type tied at max_freq in the
    # final round -- every other job packs into those gaps "for free"
    frame = (max_freq - 1) * (cooldown + 1) + count_max
    # if there are enough distinct types to fill every gap, no idle slots
    # are needed at all and the answer is simply the job count
    return max(frame, len(jobs))

Key Functions & Tricks

• collections.Counter(jobs) — tallies frequency of each model type in one pass.
• max(counts.values()) — finds the most-constrained job type's frequency.
• sum(1 for freq in counts.values() if freq == max_freq) — counts ties at the max frequency, needed because ties each contribute a slot in the final round.
• Frame formula — (max_freq - 1) * (cooldown + 1) + count_max models the schedule as gaps around the most frequent type instead of simulating time step by step.
• max(frame, len(jobs)) — falls back to the raw job count once there's enough variety to eliminate all idle time.

How to Recognize This Pattern