Fewest time slots when each job type needs a cooldown

Heaps and priority queues Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
from collections import Counter
jobs, gap = "AAABBC", 2
counts = Counter(jobs).values()
most = max(counts)
tied = sum(1 for c in counts if c == most)
print(max(len(jobs), (most - 1) * (gap + 1) + tied))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 7

Right: A _ _ A _ _ A needs 7 slots, and B and C fit into the gaps.

The busiest letter sets the frame, and the other jobs only add slots when the gaps are full.

Why not the others?
  • B 6. A appears three times with two slots between each, which already needs 7.
  • C 9. The last A needs no gap after it.

30-second answer

Greedy: in each round of gap + 1 slots, run the letters with the most jobs left, one each, using a max-heap of remaining counts. Idle slots fill a round only if more work remains. Each job is popped and pushed once per run: O(n log 26) = O(n), and the heap holds at most 26 counts: O(1) space. There is also a closed form: max(n, (most - 1) · (gap + 1) + letters tied for most).

Practise saying it · 60 s. No recording, just a timer

Explain the cooldown scheduling greedy.

Say your answer out loud, then check which of these points you covered:

  • Max-heap of counts
  • Rounds of gap + 1
  • Closed form as a check

Deep dive

Taking the most frequent letter first is what keeps idle slots to a minimum.

The closed form is a great check, and a confident interview answer once you can explain it.

With only 26 letters, the heap never holds more than 26 items.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
from collections import Counter
from heapq import heapify, heappop, heappush


def fewest_slots(jobs: str, gap: int) -> int:
    left = [-c for c in Counter(jobs).values()]  # max-heap by negation
    heapify(left)
    slots = 0
    while left:
        ran: list[int] = []
        for _ in range(gap + 1):
            if left:
                ran.append(heappop(left) + 1)  # one job of that letter
        for c in ran:
            if c < 0:
                heappush(left, c)
        slots += gap + 1 if left else len(ran)
    return slots

Common mistakes

  • Counting idle slots in the final round when no work remains.
  • Forgetting that the answer is at least the number of jobs.

Senior take & follow-ups

Give the greedy first, then the formula as a check; it shows depth.

Follow-up questions

Think of your answer first, then open the hint.

  1. Where does the closed form come from?

    Show hint

    The most frequent letter needs most - 1 full gaps after its first run; letters tied with it add one slot each at the end.

  2. What if you must output the order?

    Show hint

    Record the letters popped each round, plus 'idle' markers.

What each operation costs: Min Heap · Max Heap · Heap Operations · Priority Queue

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.