~25 minutes · Day 49 · heap scheduling · Python
Tonight's target is Task Scheduler. Interviewers like it because the problem looks like calendar math, but the real skill is choosing the next legal piece of work. If a task is still cooling down, it cannot be chosen. Among the tasks that are legal, the one with the most remaining copies is the one most likely to create future idle time, so it gets priority now.
Always run the most frequent available task; a cooldown queue holds tasks until they are legal again.
That is the whole pattern. A heap answers "which legal task has the largest remaining count?" A queue answers "which cooling task becomes legal next?" If the heap is empty but the queue still has work, the CPU idles for that interval.
Python gives you the two structures this pattern needs:
heapq — a min-heap. To behave like a max-heap, store counts as negative numbers.deque — a queue with fast appends and pops from the left.The heap keeps only tasks that are legal to run now. The cooldown queue keeps tasks that still have remaining copies, paired with the first time they may re-enter the heap.
The heap chooses among legal tasks only; the queue protects the cooldown rule.
The problem: given task letters and a cooldown n, return the fewest CPU intervals needed to run every task. The direct simulation is to advance time one interval at a time, scan every task type, ignore illegal tasks, and choose the legal task with the largest remaining count.
while work_remains:
scan every task type
choose the legal task with the largest count
run it, or idle if none is legal
This works, but it keeps re-scanning the same task types every interval. If T is the answer length and u is the number of distinct task types, that scan is O(T · u). The heap version keeps the current best legal task ready without re-scanning everything.
With from collections import Counter, deque and import heapq above it, the core loop is short:
def least_interval(tasks, n):
heap = [-c for c in Counter(tasks).values()]
heapq.heapify(heap) # biggest count is smallest negative
wait = deque() # (ready_time, negative_count)
time = 0
while heap or wait:
time += 1
while wait and wait[0][0] <= time:
heapq.heappush(heap, wait.popleft()[1])
if heap:
count = heapq.heappop(heap) + 1 # run one copy
if count: wait.append((time + n + 1, count))
return time
Notice the separation: the heap never holds illegal tasks. Once a task runs, it leaves the heap. If it still has copies left, it sits in wait until time + n + 1, because there must be n full intervals between two equal tasks.
For cooldown n = 2, A can return only at time + n + 1.
Reorganize String: rearrange a string so no two adjacent characters are equal.
Before reading the reveal: say the pattern out loud. What lives in the heap? What gets held out of the heap for one turn?
This is Task Scheduler with cooldown n = 1. The heap holds available characters by remaining count. After placing a character, hold that same character out for one position before it can return. If the heap empties while a held character still has remaining copies, no valid rearrangement exists.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan each interval) | O(T · u) | O(u) |
| Heap plus cooldown queue | O(T log u) | O(u) |
Here T is the number of CPU intervals returned, and u is the number of distinct task types. The point is not memorizing this exact loop; the point is remembering what each structure is responsible for.
1. What does available mean in the invariant?
2. Why can this schedule violate cooldown?
if heap:
count = heapq.heappop(heap) + 1
if count:
heapq.heappush(heap, count)3. Which sentence names this scheduling pattern?
4. What lives in the cooldown queue?
Solve Task Scheduler on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:
Watch NeetCode — Task Scheduler after your attempt, as the compare step. Pause at the first heap decision and check whether it matches your prediction.
Stuck or curious? Ask your teacher (the agent) — that's what it's for.