Start learning free

LESSON 387 OF 536 · HEAP

Task Scheduler in Java: O(T log 26) with a Max-Heap and a Cooldown Queue

Practice O(T log 26) Read the full explanation

A CPU has to run a list of tasks. Each task is an uppercase letter from A to Z; equal letters are copies of the same task. Running one task takes one unit of time, and in each unit the CPU either runs one task or stays idle.

There is a cooldown: two copies of the same task must be at least n units apart, so after running a task the CPU needs n other units (other tasks, or idle) before it can run that task again. The tasks can run in any order.

Return the fewest units of time the CPU needs to run all the tasks.

 

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: One best order is A B idle A B idle A B.
After an A, two other units must pass before the next A, and B has the same rule. With only two kinds of task, the CPU has to idle twice.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: With no cooldown, any order works, for example A A A B B B, and no unit is idle.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: One best order is A B C A D E A F G A idle idle A idle idle A.
The six A's need two units between each other; the other tasks fill the first gaps, and the CPU idles in the rest.

 

Constraints:

  • 1 <= tasks.length <= 105
  • Every task is an uppercase English letter.
  • 0 <= n <= 100

Note:

Your algorithm should run in O(T log 26) time, where T is the number of tasks (log 26 because a heap here never holds more than 26 kinds of task), and use O(1) extra space: at most 26 counts.

The tutorial simulates the CPU with a max-heap: in each unit, run the task with the most copies left, then let it wait in a queue until its cooldown is over. When no task is ready, the time jumps straight to the moment the first waiting task is ready again. (The answer also has a counting shortcut: if the most frequent task appears m times and c tasks appear that often, it is the bigger of tasks.length and (m - 1) · (n + 1) + c.)

STEP 1 OF 15
    Ctrl + Enter to check

    JAVA · HEAP

    Task Scheduler in Java, explained

    Problem overview

    A CPU has a list of tasks, each an uppercase letter; equal letters are copies of the same task. Running one task takes one unit of time, and in each unit the CPU either runs a task or stays idle. Two copies of the same task must be at least n units apart: after running a task, n other units (other tasks or idle time) must pass before it can run again. The tasks can run in any order.

    The method leastInterval receives tasks as a char[] and the cooldown n, and returns the fewest units of time needed to run everything.

    • AAABBB with n = 2 gives 8: A B idle A B idle A B. With only two kinds of task the CPU has to idle twice.
    • AAABBB with n = 0 gives 6: no cooldown, so no idling.
    • AAAAAABCDEFG with n = 2 gives 16: A B C A D E A F G A idle idle A idle idle A. The six A's need two units between each other, and the other tasks fill only the first gaps.

    The statement asks for O(T log 26) time, where T is the number of tasks, and O(1) extra space: at most 26 counts.

    Approach: always run the task with the most copies left

    Only the number of copies of each task matters, not which letter it is. So the first step is to count the letters: an int[26] where index task - 'A' holds the count.

    The CPU is then simulated. Which task should run in a free unit? The one with the most copies left: its copies need the most room between them, so starting them early leaves the fewest idle units at the end. A max-heap of counts gives that task in O(log 26).

    After a task runs, it can't run again for a while. So it waits in a queue, together with the time at the end of which its cooldown is over. Tasks join the queue in the order they run, so they also leave it in order of their ready time, and a plain FIFO queue is enough. When the heap is empty but tasks are still cooling down, the CPU idles. Instead of counting idle units one by one, the time jumps straight to the moment the first waiting task is ready.

    Here is the simulation for AAABBB with n = 2. Each line shows the time after that turn, what happened, the heap and the number of tasks cooling:

    time 1: run a task, 2 left | heap [3] cooling 1
time 2: run a task, 2 left | heap [] cooling 2
time 3: jump to 3, back in heap with 2 | heap [2] cooling 1
time 4: run a task, 1 left, back in heap with 2 | heap [2] cooling 1
time 5: run a task, 1 left | heap [] cooling 2
time 6: jump to 6, back in heap with 1 | heap [1] cooling 1
time 7: run a task, 0 left, back in heap with 1 | heap [1] cooling 0
time 8: run a task, 0 left | heap [] cooling 0

    The "jump" lines are the idle units, and the final time is 8. The two jumps happen at units 3 and 6.

    Step by step

    1. Count the copies. Declare int[] count = new int[26]; Java fills it with zeros.
    2. Loop over the tasks with for (char task : tasks) and do count[task - 'A']++. Letters are numbers in alphabetical order, so subtracting 'A' turns A into 0, B into 1, up to Z as 25.
    3. Build the heap: a PriorityQueue<Integer> named heap with the comparator (x, y) -> y - x, so the biggest count comes out first.
    4. Fill it: for each c in count, add c to the heap when c > 0. Letters that never appear have nothing to run.
    5. Create the waiting queue: Queue<int[]> cooling = new LinkedList<>(). Each entry is {left, readyTime}: the copies left and the time unit at whose end the cooldown is over.
    6. Start the clock: int time = 0. It counts the units used so far and ends as the answer.
    7. Loop while there is work: !heap.isEmpty() || !cooling.isEmpty(). The job is done only when nothing is ready and nothing is cooling.
    8. Start a new unit: time++.
    9. If the heap is empty, nothing can run, so the CPU idles until the first waiting task is ready: time = cooling.peek()[1]. This counts all the idle units at once.
    10. Otherwise run a task. int left = heap.poll() - 1 takes the biggest count and uses up one copy.
    11. Queue it if copies remain. If left > 0, add new int[]{left, time + n} to cooling. A task run at time can run again at time + n + 1, after n other units. Tasks with no copies left are done.
    12. Release a task whose cooldown is over. If cooling is not empty and cooling.peek()[1] == time, take it out with poll() and add its count, item [0], back to heap.
    13. Return time, the unit in which the last task ran.

    The solution in Java

    class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char task : tasks) {
            count[task - 'A']++;
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>((x, y) -> y - x);
        for (int c : count) {
            if (c > 0) {
                heap.add(c);
            }
        }
        Queue<int[]> cooling = new LinkedList<>();
        int time = 0;
        while (!heap.isEmpty() || !cooling.isEmpty()) {
            time++;
            if (heap.isEmpty()) {
                time = cooling.peek()[1];
            } else {
                int left = heap.poll() - 1;
                if (left > 0) {
                    cooling.add(new int[]{left, time + n});
                }
            }
            if (!cooling.isEmpty() && cooling.peek()[1] == time) {
                heap.add(cooling.poll()[0]);
            }
        }
        return time;
    }
}

    Java details worth a closer look:

    • char arithmetic. task - 'A' is an int: the difference of the two character codes, so it can index the array directly.
    • Max-heap through a comparator. PriorityQueue is a min-heap by default. (x, y) -> y - x reverses it. Subtraction is safe here because counts are small.
    • Queue and LinkedList. The variable has the interface type Queue<int[]>, and LinkedList implements it. add puts an entry at the back, peek reads the front without removing it, and poll removes it.
    • Auto-unboxing. heap.poll() - 1 unboxes the Integer to an int. heap.add(c) boxes an int back. The heap is never empty at the poll, because that line is in the else branch of heap.isEmpty().
    • Arrays as entries. A two-element int[] is a light way to keep a count and a time together without a class.

    Another way: counting

    The simulation also has a closed form. If the most frequent task appears m times and c different tasks appear that often, the answer is the larger of tasks.length and (m - 1) * (n + 1) + c. The first term lays out m - 1 full blocks of n + 1 units and a last partial block holding the c most frequent tasks. The second covers the case where there are so many other tasks that no idling is needed.

    static int shortcut(char[] tasks, int n) {
    int[] count = new int[26];
    for (char t : tasks) count[t - 'A']++;
    int m = 0;
    for (int c : count) m = Math.max(m, c);
    int c = 0;
    for (int x : count) if (x == m) c++;
    return Math.max(tasks.length, (m - 1) * (n + 1) + c);
}

    This gives 8 for AAABBB with n = 2, 16 for the six A's example and 6 for AAABBB with n = 0, the same as the heap solution. The lesson builds the simulation, which shows how the cooldown actually works.

    Complexity

    Time: O(T log 26). Counting is O(T). Each simulated turn runs one task, with one heap poll and at most one heap add, and the heap never holds more than 26 counts, so each costs O(log 26). The idle jumps skip units without extra turns, so there are at most T turns that run a task, and the number of jump turns is bounded by the same number.

    Space: O(1). The count array has 26 entries, the heap and the queue each hold at most 26 entries, and nothing grows with T.

    Edge cases and common mistakes

    • One task. A with n = 100 gives 1. No second copy exists, so there is nothing to wait for.
    • Two copies. AA with n = 3 gives 5: A, three idle units, A.
    • A large cooldown. AAABBB with n = 50 gives 104: the second round starts 51 units after the first, and the third 51 after that, so the last B runs at unit 104.
    • All different. ABCD with n = 5 gives 4, since no task repeats.
    • Enough other tasks. AAABBC with n = 2 gives 7, with idle time only where nothing else is ready.
    • Using a min-heap. Running the task with the fewest copies left first can leave the long chains for the end, where they add idle units.
    • Off-by-one in the cooldown. Storing time + n + 1 or comparing with time + 1 makes tasks wait one unit too long or run one unit too soon.
    • Counting idle units one at a time. It works, but the jump keeps the loop short when n is large.

    Testing

    • AAABBB, n = 2 gives 8.
    • AAABBB, n = 0 gives 6.
    • AAAAAABCDEFG, n = 2 gives 16.
    • A, n = 100 gives 1.
    • AA, n = 3 gives 5.

    In the lesson's code the input is a char[], so AAABBB stands for {'A', 'A', 'A', 'B', 'B', 'B'}.

    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free