Problem 18.4 · Heaps and Priority QueuesMedium

Task Scheduler

What it teaches: Greedy with a heap: always run the task with the most copies left; then see the counting formula behind it.

Practise it on judges as “Task Scheduler”.

The problem

Tasks are letters; each takes one time unit. The same letter must be separated by at least n units (the CPU can idle). Return the minimum number of units to finish all tasks.

Example 1

Input: tasks = [A, A, A, B, B, B], n = 2
Output: 8

A B idle A B idle A B.

Constraints

1 ≤ tasks ≤ 10⁴
0 ≤ n ≤ 100

Pattern clues in the wording

→ Cooldown between equal items
→ Schedule the most frequent first

These clues point to Top K with a Heap: Keep a heap of size k: a min-heap for the k largest, a max-heap for the k smallest.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	tasks = ["A","A","A","B","B","B"] n = 2	8
2	tasks = ["A","C","A","B","D","B"] n = 1	6
3	tasks = ["A","A","A","B","B","B"] n = 0	6

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Heap simulation · O(T log 26)2. Counting formula · O(T)

Heap simulation

Time O(T log 26) Space O(26)

Each round of n + 1 slots, pop up to n + 1 different tasks with the most copies left, run them, and push back those that still have copies. A full round costs n + 1 units unless it's the last.

Approach 1

import java.util.*;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char t : tasks) count[t - 'A']++;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for (int c : count) if (c > 0) pq.offer(c);
        int time = 0;
        while (!pq.isEmpty()) {
            List<Integer> left = new ArrayList<>();
            int ran = 0;
            for (int slot = 0; slot <= n && !pq.isEmpty(); slot++) {
                int c = pq.poll();
                if (c > 1) left.add(c - 1);
                ran++;
            }
            for (int c : left) pq.offer(c);
            time += pq.isEmpty() ? ran : n + 1;
        }
        return time;
    }
}

Verdict: Shows why the greedy is right.

Counting formula

Time O(T) Space O(26)

Let maxCount be the highest frequency and tied the number of letters with it. The answer is max(tasks.length, (maxCount − 1) × (n + 1) + tied).

Approach 2

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        int max = 0;
        for (char t : tasks) max = Math.max(max, ++count[t - 'A']);
        int tied = 0;
        for (int c : count) if (c == max) tied++;
        return Math.max(tasks.length, (max - 1) * (n + 1) + tied);
    }
}

Verdict: Optimal once you see the frame shape.

Before you submit

Edge cases and common mistakes

Test these inputs

n = 0 (no idling)
Many different letters (no idling needed)

Mistakes people make

Forgetting the max with tasks.length when there are enough tasks to fill every gap.

Interview

Follow-up questions

How do you output an actual schedule?