Room 04 · The Grind — Heap / Priority Queue

Task Scheduler

MEDIUM✓ CHIP-TIMEDLC #621 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: CPU tasks each need a cooldown of n idle-or-other-task slots before the same task letter can run again — schedule everything (idle ticks allowed) and report the fewest total time units needed.

A list of CPU tasks arrives, each labeled with a letter, along with a cooldown n — once a given task letter runs, that same letter can't run again until n other slots, idle or otherwise, have passed.

Every unit of time either runs exactly one task or sits idle, and idle time still counts toward the total — the schedule has to cover every task in the list, in any order that respects the cooldown.

The answer is the fewest total time units needed to get every task done at least once, cooldowns and all.

task counts run up to several thousand
cooldown n can be zero, meaning no restriction at all
idle slots count toward the total time
every task in the list must run exactly once

EX 01

tasks = ["A", "A", "A", "B", "B", "B"] · n = 2

→ 8

the classic two-task shape

EX 02

tasks = ["A", "A", "A", "B", "B", "B"] · n = 0

→ 6

no cooldown at all, just run everything back to back

EX 03

tasks = ["A", "A", "A", "A", "A", "A", "B", "C", "D", "E", "F", "G"] · n = 2

→ 16

one dominant task with plenty of fillers

The hintstake only what you need

HINT 1 THE NUDGE

The task that shows up the most is the real bottleneck — it forces cooldown gaps that the rarer tasks may or may not be able to fill.

HINT 2 THE STRUCTURE

Picture rounds of length n+1: fill each round with whatever's most available right now, and only fall back to idle when literally nothing has finished its cooldown.

HINT 3 ONE STEP FROM THE ANSWER

A max-heap of remaining counts drives the picks; a cooldown queue holds tasks until their wait is up and hands them back to the heap exactly when they become eligible again.

Coach's boardthe pattern, step by step

FILLING THE COOLDOWNPATTERN · MAX-HEAP + COOLDOWN QUEUEtasks = [A,A,A,B,B,B] · n = 2

STEP 1

A and B each appear 3 times, and a cooldown of n=2 means the same letter can't run again until 2 other slots pass.

STEP 1 / 9 · ← → WORK TOO

The splitstwo paces, two languages

grind/task-scheduler.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = collections.Counter(tasks)
        heap = [-c for c in counts.values()]
        heapq.heapify(heap)
        time = 0
        q = collections.deque()  # (releaseTime, remainingCountNegated)
        while heap or q:
            time += 1
            if heap:
                c = heapq.heappop(heap) + 1  # one unit done
                if c != 0:
                    q.append((time + n, c))
            if q and q[0][0] == time:
                heapq.heappush(heap, q.popleft()[1])
        return time

TIME O(TOTAL LOG 26)SPACE O(26)PYTHON · RACE PACE · 16 LN

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = collections.Counter(tasks)
        cooldown = {}  # task -> the minute it becomes available again
        remaining = sum(counts.values())
        time = 0
        while remaining > 0:
            time += 1
            best = None
            for t, c in counts.items():
                if c > 0 and cooldown.get(t, 0) < time:
                    if best is None or c > counts[best]:
                        best = t
            if best is not None:
                counts[best] -= 1
                cooldown[best] = time + n
                remaining -= 1
        return time

TIME O(TOTAL · 26)SPACE O(1)PYTHON · TRAINING PACE · 18 LN

class Solution {
    public int leastInterval(String[] tasks, int n) {
        Map<String, Integer> counts = new HashMap<>();
        for (String t : tasks) {
            counts.merge(t, 1, Integer::sum);
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        heap.addAll(counts.values());
        Deque<int[]> q = new ArrayDeque<>(); // [releaseTime, remainingCount]
        int time = 0;
        while (!heap.isEmpty() || !q.isEmpty()) {
            time++;
            if (!heap.isEmpty()) {
                int c = heap.poll() - 1;
                if (c != 0) {
                    q.addLast(new int[] { time + n, c });
                }
            }
            if (!q.isEmpty() && q.peekFirst()[0] == time) {
                heap.offer(q.pollFirst()[1]);
            }
        }
        return time;
    }
}

TIME O(TOTAL LOG 26)SPACE O(26)JAVA · RACE PACE · 25 LN

class Solution {
    public int leastInterval(String[] tasks, int n) {
        Map<String, Integer> counts = new HashMap<>();
        for (String t : tasks) {
            counts.merge(t, 1, Integer::sum);
        }
        Map<String, Integer> cooldown = new HashMap<>();
        int remaining = tasks.length;
        int time = 0;
        while (remaining > 0) {
            time++;
            String best = null;
            for (Map.Entry<String, Integer> e : counts.entrySet()) {
                String t = e.getKey();
                int c = e.getValue();
                if (c > 0 && cooldown.getOrDefault(t, 0) < time) {
                    if (best == null || c > counts.get(best)) {
                        best = t;
                    }
                }
            }
            if (best != null) {
                counts.put(best, counts.get(best) - 1);
                cooldown.put(best, time + n);
                remaining--;
            }
        }
        return time;
    }
}

TIME O(TOTAL · 26)SPACE O(1)JAVA · TRAINING PACE · 30 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED