← All Problems

6. Schedule Training Jobs with GPU Cooldown

General Pattern Hard Greedy + Counting / Task Scheduler
Grounding: (Originally problem 41 in ai-labs-coding.) General: task-scheduling-with-cooldown (the "Task Scheduler" pattern) is a standard greedy/counting pattern relevant to any system that rate-limits repeated job types on shared hardware. Not tied to a specific reported example from Anthropic, OpenAI, DeepMind, or Mistral interviews in this batch's research.

Problem

A shared GPU can only run one job per time unit, and after finishing a job of a given type, that same job type must sit idle for a fixed cooldown period, for example to let thermal throttling or a shared checkpoint lock clear, before the GPU can run another job of that type again.

Given the queue of job types (order irrelevant, only counts per type matter) and the cooldown, find the minimum number of time units to run every job. This must run in O(n) time using type-frequency counting, not an explicit simulation with a priority queue.

Source: src/6_schedule_jobs_gpu_cooldown.py

def min_schedule_length(job_types: list[str], cooldown: int) -> int:
    ...

Examples:
>>> min_schedule_length(["A", "A", "A", "B", "B", "B"], 2)
8

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

Step-by-Step Approach

  1. Notice that the schedule is bottlenecked by whichever job type appears most often, since every occurrence of that type after the first needs a full cooldown gap before it can run again.
  2. Count how many times each job type appears, and find the maximum frequency (max_freq) among all types.
  3. Picture laying out max_freq - 1 full "cooldown cycles" for the most frequent type, each cycle being one job slot plus cooldown idle-or-other-job slots, i.e. cooldown + 1 slots per cycle.
  4. After those cycles, one final slot is needed to place the last occurrence of the max-frequency type. But if multiple types are tied for the max frequency, each of them also needs a slot in that final cycle, since they all run out of cooldown room at the same time.
  5. That gives a lower bound: (max_freq - 1) * (cooldown + 1) + count_of_types_at_max_freq. Other, less-frequent job types slot into the idle gaps of this structure for free, without ever increasing the total length.
  6. This lower bound only applies when idle slots are actually needed. If there's enough job-type variety to fill every cooldown gap with a different job (no idle time at all), the true answer is simply the total job count. Take the max of the two to cover both cases.

The key insight is that you never need to simulate the schedule slot by slot: the answer is fully determined by two numbers, the max frequency and how many types share it, because that's exactly what fixes how much idle time the most-repeated type forces onto the schedule.

Reference solution

from collections import Counter


def min_schedule_length(job_types: list[str], cooldown: int) -> int:
    if not job_types:
        return 0
    # frequency-counting formula (no simulation needed): the most frequent type
    # dictates (max_freq - 1) full cooldown cycles, plus one slot per type tied
    # for max_freq to close out the last cycle. Idle-free schedules (enough type
    # variety to fill every cooldown gap) are capped below by len(job_types).
    counts = Counter(job_types)
    max_freq = max(counts.values())
    num_at_max = sum(1 for freq in counts.values() if freq == max_freq)
    return max(len(job_types), (max_freq - 1) * (cooldown + 1) + num_at_max)

Key Functions & Tricks

  • collections.Counter(job_types) — O(n) frequency count of each job type
  • max_freq = max(counts.values()) — identifies the bottleneck type that forces the most cooldown gaps
  • (max_freq - 1) * (cooldown + 1) — each repeat of the busiest type after the first needs a full cooldown + 1-slot cycle around it
  • num_at_max — types tied for the max frequency all need a slot in the final cycle, not just one
  • max(len(job_types), ...) — the cooldown-driven formula is only a lower bound; enough job-type variety can fill every gap, so the true floor is never below the plain job count

How to Recognize This Pattern

The signal is "schedule repeated items from a fixed set with a mandatory cooldown/spacing constraint between repeats of the same item," the classic LeetCode "Task Scheduler" shape. Whenever the constraint is symmetric across all instances of a type (same cooldown regardless of which other jobs fill the gap), the answer reduces to a frequency-counting formula rather than requiring an explicit greedy simulation with a max-heap, though the heap-based simulation is a valid, slightly more expensive (O(n log 26) or O(n log k)) alternative that also directly produces the schedule itself, not just its length. Common variations include needing the actual sequence of job types (not just the count, which does require simulation), a per-type cooldown instead of one global cooldown, or jobs with variable duration instead of one time unit each. A common pitfall is forgetting the max(len(job_types), ...) floor and returning a value smaller than the job count when there's enough variety to need no idle time at all, or forgetting to count *all* types tied for the max frequency, not just one.

← Previous Next →