Start learning free

LESSON 386 OF 535 · HEAP

Task Scheduler in C++: 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 16
    Ctrl + Enter to check

    C++ · HEAP

    Task Scheduler in C++, explained

    Problem overview

    A CPU runs a list of tasks, given as a vector<char> named tasks. Each task is an uppercase letter, and equal letters are copies of the same task. Running one task takes one unit of time, and in each unit the CPU runs one 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) must pass before that task runs again. The tasks can run in any order.

    leastInterval receives tasks and the cooldown n and returns the fewest units of time needed to run everything.

    With three copies each of A and B and n = 2, the answer is 8: one best order is A B idle A B idle A B. With n = 0 the same tasks need only 6 units, in any order. With six copies of A, one each of B to G and n = 2, the answer is 16: A B C A D E A F G A idle idle A idle idle A.

    The statement asks for O(T log 26) time, where T is the number of tasks, since a heap here never holds more than 26 kinds of task, and O(1) extra space, since there are at most 26 counts.

    Approach: always run the task with the most copies left

    Only the number of copies of each task matters, not the order in the input, so the first step is to count the letters.

    Then simulate the CPU, one unit at a time, with one rule: run the task that has 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 has to wait. Running it at time t lets it run again at time t + n + 1, after n other units. So it goes into a queue of cooling tasks as the pair {left, readyTime}: the copies it has left, and the unit at whose end its cooldown is over, which is t + n. Tasks enter the queue in the order they run, so they leave it in order of ready time, and only the front can be ready.

    When the heap is empty but tasks are still cooling, the CPU has nothing to run. Instead of counting idle units one by one, the time jumps straight to the ready time of the first waiting task, which counts all the idle units at once.

    Here is the simulation for three As and three Bs with n = 2, as a trace of the loop:

    time=1: run task with 3 copies, 2 left
time=2: run task with 3 copies, 2 left
time=3: idle until here
  ready again: 2 copies
time=4: run task with 2 copies, 1 left
  ready again: 2 copies
time=5: run task with 2 copies, 1 left
time=6: idle until here
  ready again: 1 copies
time=7: run task with 1 copies, 0 left
  ready again: 1 copies
time=8: run task with 1 copies, 0 left

    The first task to run (the A, at time 1) becomes ready again at the end of unit 3. Units 1 and 2 run the two tasks, unit 3 is idle, and the cooled-down task is back in the heap for unit 4. The last task runs at unit 8, so the answer is 8.

    For six As and six other single tasks, the trace ends with jumps. At time 10 the A runs its fifth copy, and its next copy is ready at the end of unit 12, so units 11 and 12 are idle and the loop moves from 10 straight to 12. The same happens between units 13 and 16, and the answer is 16.

    Step by step

    1. Create count, a vector<int> of 26 zeros, one per letter: index 0 for A up to 25 for Z.
    2. Loop over tasks with a char task.
    3. Count each task with count[task - 'A']++. Letters are stored as consecutive numbers, so subtracting 'A' turns A into 0 and Z into 25.
    4. Declare the heap: priority_queue<int> heap, a max-heap, so the biggest count is on top.
    5. Loop over count with an int c.
    6. Push the non-zero counts: a letter that never appears has nothing to run.
    7. Declare cooling as queue<pair<int, int>>: the waiting tasks as {left, readyTime}, read with .first and .second.
    8. Start time at 0. It counts the units used so far, and is the answer when everything has run.
    9. Loop while !heap.empty() || !cooling.empty(). The work is done only when nothing is ready and nothing is cooling.
    10. Add one to time: a new unit starts.
    11. If the heap is empty, the CPU idles until the first cooling task is ready: set time to cooling.front().second.
    12. Otherwise run a task: left is heap.top() - 1, the copies remaining after this run, and heap.pop() removes the entry.
    13. If copies remain, push {left, time + n} onto cooling. A task with no copies left is finished and isn't queued.
    14. Release a ready task: if cooling isn't empty and its front has ready time equal to time, move its count back into heap and pop the queue. The emptiness check comes first, so the front is never read from an empty queue.
    15. Return time, the unit in which the last task ran.

    The solution in C++

    class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> count(26, 0);
        for (char task : tasks) {
            count[task - 'A']++;
        }
        priority_queue<int> heap;
        for (int c : count) {
            if (c > 0) {
                heap.push(c);
            }
        }
        queue<pair<int, int>> cooling;
        int time = 0;
        while (!heap.empty() || !cooling.empty()) {
            time++;
            if (heap.empty()) {
                time = cooling.front().second;
            } else {
                int left = heap.top() - 1;
                heap.pop();
                if (left > 0) {
                    cooling.push({left, time + n});
                }
            }
            if (!cooling.empty() && cooling.front().second == time) {
                heap.push(cooling.front().first);
                cooling.pop();
            }
        }
        return time;
    }
};

    The C++ details worth a closer look:

    • Letters are numbers. A char is a small integer, so task - 'A' is an int between 0 and 25 for uppercase letters. That makes a 26-element vector a simple counting table.
    • priority_queue<int> is a max-heap. Its top() is the largest value, and pop() returns nothing, so the code reads top() first and removes it second.
    • pair<int, int> holds two values read as .first and .second. The braces in cooling.push({left, time + n}) build the pair inside the call.
    • queue is first in, first out. front() is the oldest entry. Reading front() of an empty queue is undefined behaviour, which is why the second if tests !cooling.empty() first, and why the idle branch is safe: the loop only runs while one of the two containers has something, and an empty heap means the queue has an entry.
    • The variable named time hides the C library function of the same name inside this function. That is allowed, and the function never needs the library one.
    • time = cooling.front().second never moves time backwards: tasks are queued one per unit, so their ready times are all different and increasing, and each one is released in the very unit its ready time is reached. A task still waiting therefore always has a ready time later than the unit before the jump.

    Complexity

    Time: O(T log 26). Counting is O(T). Every unit of the loop either runs a task, which takes one heap pop and at most one push, or jumps over idle time. Idle jumps are followed at once by a task being released, so the loop makes at most one turn per task run plus one per idle stretch, which is at most T turns of each kind. The heap holds at most 26 counts, so each heap operation is O(log 26).

    Space: O(1). count has 26 entries, the heap at most 26, and the queue at most 26 pairs.

    Edge cases and common mistakes

    • No cooldown. With n = 0 a task is queued with ready time equal to the current unit and is released at once, so no unit is idle. Three As and three Bs give 6.
    • A single task. {'A'} with n = 5 gives 1: there is no second copy to wait for. {'A', 'A'} with n = 3 gives 5: A, three idle units, A.
    • Cooldown longer than the number of tasks. {'A', 'B', 'C'} with n = 50 gives 3. Each task is different, so none ever waits for itself.
    • Only the cooldown idles. The answer can never be smaller than tasks.size(). When enough different tasks exist to fill every gap, the answer equals it exactly: three As, three Bs, three Cs, two Ds and one E with n = 2 give 12, with no idle unit.
    • Running the smallest count first. If the CPU picks a task with few copies left, the most frequent task is left for the end and is forced to idle. Always picking the biggest count avoids that.
    • Cooldown off by one. A task run at unit t can run again at t + n + 1. Storing time + n as the unit at whose end the cooldown is over, and releasing it when time reaches that value, gives exactly n units in between.
    • Counting idle units one by one. The jump keeps the loop short even for n = 100.

    Testing

    • {'A', 'A', 'A', 'B', 'B', 'B'} with n = 2 gives 8.
    • {'A', 'A', 'A', 'B', 'B', 'B'} with n = 0 gives 6.
    • Six As and one each of B, C, D, E, F, G with n = 2 gives 16.
    • {'A'} with n = 5 gives 1.
    • {'A', 'A'} with n = 3 gives 5.
    • {'A', 'B', 'C'} with n = 50 gives 3.
    • Three As, three Bs, three Cs, two Ds and one E with n = 2 gives 12.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free