Start learning free

LESSON 390 OF 539 · HEAP

Task Scheduler in C#: Max-Heap and Cooldown Queue, O(T log 26)

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

    The method LeastInterval receives a char[] of tasks, each an uppercase letter from A to Z, and an int n, the cooldown. Equal letters are copies of the same task. Running a task takes one unit of time, and in each unit the CPU either runs one task or idles. Two copies of the same task must be at least n units apart: after running a task, n other units (other tasks or idle ones) must pass before it can run again. The tasks may run in any order, and the method returns the fewest units of time needed.

    For AAABBB with n = 2 the answer is 8: A B idle A B idle A B. With only two kinds of task the CPU has to idle twice. With n = 0 the same tasks take 6 units, since any order works. For AAAAAABCDEFG with n = 2 the answer is 16: the six A's need two units between each other, the other tasks fill the first gaps, and the CPU idles in the rest.

    Approach: always run the task with the most copies left

    Only the number of copies of each letter matters, not their order in the input, so the first step is counting them. The 26 counts are all the state the problem has.

    Then the CPU is simulated. At each unit, run the task with the most copies left. Those copies need the most room between them, so starting them early leaves the fewest idle units at the end. A max-heap gives that task quickly, and since there are at most 26 kinds, the heap never holds more than 26 entries, which is where log 26 in the time bound comes from.

    A task that just ran can't run again for n units, so it waits in a queue of cooling tasks. Tasks enter that queue in the order they run, so they leave it in order of ready time, and the front is always the first one that will be ready. Each queue entry is {left, readyTime}: how many copies the task has left, and the time at whose end its cooldown is over. A task run at time gets readyTime = time + n and can run again one unit later, after n other units.

    If the heap is empty but tasks are still cooling, the CPU must idle. Rather than step through the idle units one by one, the code jumps time straight to the front task's ready time.

    For AAABBB with n = 2, the counts are 3 and 3. The loop goes like this:

    timewhat happens
    1a task runs (2 copies left), and waits until time 3
    2the other task runs (2 left), and waits until time 4
    3the heap is empty: idle. The first task is ready and goes back to the heap
    4it runs (1 left). The second task is ready and goes back to the heap
    5the second task runs (1 left)
    6idle again; the first task is ready
    7it runs (0 left). The second task is ready
    8it runs (0 left). Nothing is left, so the answer is 8

    Step by step

    1. Count the letters. count is an int[] with 26 places. A new int array starts filled with zeros.
    2. Loop over the tasks with foreach (char task in tasks) and add one at index task - 'A'. Characters are numbers underneath, so 'A' - 'A' is 0, 'B' - 'A' is 1, up to 25 for 'Z'.
    3. Build the max-heap. PriorityQueue<int, int> is a min-heap by default, so it is created with Comparer<int>.Create((x, y) => y - x), which makes the biggest priority come out first.
    4. Fill it. For each c in count, if c > 0, call heap.Enqueue(c, c). The count is both the element and its priority, and letters that never appear (count 0) are left out.
    5. Create the cooling queue, a Queue<int[]>, and time, an int starting at 0.
    6. Loop while work remains: heap.Count > 0 || cooling.Count > 0. The job is done only when nothing waits to run and nothing is cooling.
    7. Start a unit: time++.
    8. If the heap is empty, the CPU idles until the front of cooling is ready: time = cooling.Peek()[1].
    9. Otherwise run a task: left = heap.Dequeue() - 1 is how many copies it has after this run.
    10. Start its cooldown if left > 0: cooling.Enqueue(new int[]{left, time + n}). A task with no copies left is finished and isn't queued.
    11. Release a ready task. If cooling.Count > 0 && cooling.Peek()[1] == time, dequeue it and put its count back into the heap. Check that the queue is not empty before reading its front. Only the front can be ready, because the queue is in order of ready time.
    12. Return time, the unit in which the last task ran.

    The solution in C#

    class Solution {
    public int LeastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        foreach (char task in tasks) {
            count[task - 'A']++;
        }
        PriorityQueue<int, int> heap = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y - x));
        foreach (int c in count) {
            if (c > 0) {
                heap.Enqueue(c, c);
            }
        }
        Queue<int[]> cooling = new Queue<int[]>();
        int time = 0;
        while (heap.Count > 0 || cooling.Count > 0) {
            time++;
            if (heap.Count == 0) {
                time = cooling.Peek()[1];
            } else {
                int left = heap.Dequeue() - 1;
                if (left > 0) {
                    cooling.Enqueue(new int[]{left, time + n});
                }
            }
            if (cooling.Count > 0 && cooling.Peek()[1] == time) {
                int ready = cooling.Dequeue()[0];
                heap.Enqueue(ready, ready);
            }
        }
        return time;
    }
}

    The C# details worth knowing:

    • Chars are numbers. task - 'A' is an int, so it can index the array directly. It only works for uppercase letters, which the lesson guarantees.
    • PriorityQueue is a min-heap. It is available in .NET 6 and later. Without the reversed comparer, Dequeue() would return the task with the fewest copies left. Enqueueing priorities 5, 1 and 3 dequeues the one with 1 first; with the reversed comparer it dequeues 5 first.
    • Elements and priorities. Enqueue(c, c) gives the same number as element and priority. Dequeue() returns the element, so heap.Dequeue() is the count of copies.
    • Queue<T> methods. Peek() looks at the front without removing it and Dequeue() removes it. On an empty queue both throw InvalidOperationException, which is why the code checks Count first. In the idle branch, cooling is never empty: the loop only runs while the heap or the queue has something, and the heap is empty there.
    • && and || short-circuit. In cooling.Count > 0 && cooling.Peek()[1] == time, the Peek never runs on an empty queue.
    • The jump. After time++, setting time = cooling.Peek()[1] may skip several idle units at once. For AA with n = 3, time goes from 1 straight to 4, and the second A runs at 5.

    Complexity

    Let T be the number of tasks.

    Time: O(T log 26). Counting takes O(T). Each loop turn either runs one task, so there are exactly T of those, or jumps over idle time. A jump is always followed by a release, because the front task is ready at the new time, so jumps are at most as many as runs. Every turn does a constant number of heap operations on at most 26 entries, each costing O(log 26). The cooldown n doesn't add turns, because idle units are skipped in one step.

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

    Edge cases and common mistakes

    • No cooldown. With n = 0 the answer is the number of tasks: AAABBB gives 6.
    • One task. A with n = 100 gives 1: there is no second copy to wait for.
    • Idle time is needed. AA with n = 3 gives 5: A, three idle units, A.
    • No idle units. ABCD with n = 5 gives 4, because no task repeats. AAABBC with n = 1 gives 6, because the other tasks fill every gap.
    • Many copies of one task. 100,000 copies of A with n = 100 gives 10,099,900: 99,999 * 101 + 1. The answer is far larger than the input, which still fits in an int.
    • Running the task with the fewest copies first. The big groups are left for the end, with nothing to fill their gaps, so idle time grows.
    • Reading cooling.Peek() on an empty queue throws InvalidOperationException.
    • Skipping the left > 0 check. Finished tasks would wait in the queue with 0 copies and come back into the heap.

    Testing

    • AAABBB with n = 2 gives 8; with n = 0 gives 6.
    • AAAAAABCDEFG with n = 2 gives 16.
    • A with n = 100 gives 1.
    • AA with n = 3 gives 5.
    • ABCD with n = 5 gives 4, and AAABBC with n = 1 gives 6.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free