Start learning free

LESSON 394 OF 543 · HEAP

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

    RUST · HEAP

    Task Scheduler in Rust, explained

    Problem overview

    least_interval receives tasks: Vec<char>, uppercase letters from A to Z, and a cooldown n: i32. Equal letters are copies of the same task. Each unit of time, the CPU runs one task or idles. Two copies of the same task must have at least n units between them. The tasks can run in any order, and the function returns the fewest units of time needed to run them all.

    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, because nothing is ever forced to wait. For AAAAAABCDEFG and n = 2 the answer is 16: the six A's need gaps, the other tasks fill the first ones, and the CPU idles in the rest.

    Approach: always run the task with the most copies left

    Only the number of copies of each task matters, not the order of the input. The task with the most copies left is the hardest to place, because its copies need the most room between them. Starting it early leaves the fewest idle units at the end. So the plan is a simulation: in each unit, run the task with the most copies left, then keep it waiting until its cooldown is over.

    Two structures do the work:

    • A max-heap of counts holds the tasks that are ready to run. Its top is the biggest count.
    • A queue (VecDeque) holds the tasks that are cooling down, as pairs (left, readyTime). Tasks join the queue in the order they run, so they leave it in order of ready time: the front is always the first to be ready.

    When the heap is empty but tasks are still cooling, the CPU idles. Instead of counting idle units one by one, the simulation jumps the clock straight to the moment the first waiting task is ready. There are at most 26 kinds of task, so the heap is tiny, and each task copy costs a constant number of heap operations.

    Step by step

    1. Count the copies: let mut count = [0; 26];, one place per letter, index 0 for A up to 25 for Z.
    2. Loop over tasks and add one to the count of each task's letter, at index (task as u8 - b'A') as usize. task as u8 is the letter's code and b'A' the code of A, so A maps to 0 and Z to 25. An index must be a usize.
    3. Build the heap: let mut heap = BinaryHeap::new(); and push every count c with c > 0. Letters that never appear have nothing to run.
    4. Create the cooldown queue: let mut cooling: VecDeque<(i32, i32)> = VecDeque::new();. Each entry is (left, readyTime): the copies the task has left and the time unit at whose end its cooldown is over. It can run again one unit later.
    5. Start the clock: let mut time = 0;. It counts the units used so far and is the answer once everything has run.
    6. Simulate with while !heap.is_empty() || !cooling.is_empty(). The work is done only when nothing is ready and nothing is cooling.
    7. Start a new unit: time += 1.
    8. If the heap is empty, nothing can run, so time = cooling[0].1: the idle units pass at once, up to the moment the front task is ready.
    9. Otherwise run a task: let left = heap.pop().unwrap() - 1;. The heap is not empty here, so unwrap() is safe. Running a task uses up one copy, so left is what remains.
    10. Queue it if copies remain: if left > 0, cooling.push_back((left, time + n)). A task run at time can run again at time + n + 1, after n other units.
    11. Release the front task if it is ready now: if !cooling.is_empty() && cooling[0].1 == time, take it with pop_front().unwrap() and push its count (.0) back onto the heap.
    12. Return time, the unit in which the last task ran.

    A run for AAABBB with n = 2, printing what happens in each pass of the loop:

    time 1: run a task, 2 left
time 2: run a task, 2 left
idle, jump to time 3
time 4: run a task, 1 left
time 5: run a task, 1 left
idle, jump to time 6
time 7: run a task, 0 left
time 8: run a task, 0 left
answer 8

    Units 1 and 2 run the two tasks, which both have two copies left. The heap is then empty, so the clock jumps to 3, the ready time of the first task, which goes back into the heap. Unit 3 is the idle one, and units 4 and 5 run the next copies. The same pattern repeats, and the last two copies run in units 7 and 8.

    The solution in Rust

    use std::collections::BinaryHeap;
use std::collections::VecDeque;

impl Solution {
    fn least_interval(tasks: Vec<char>, n: i32) -> i32 {
        let mut count = [0; 26];
        for task in tasks {
            count[(task as u8 - b'A') as usize] += 1;
        }
        let mut heap = BinaryHeap::new();
        for c in count {
            if c > 0 {
                heap.push(c);
            }
        }
        let mut cooling: VecDeque<(i32, i32)> = VecDeque::new();
        let mut time = 0;
        while !heap.is_empty() || !cooling.is_empty() {
            time += 1;
            if heap.is_empty() {
                time = cooling[0].1;
            } else {
                let left = heap.pop().unwrap() - 1;
                if left > 0 {
                    cooling.push_back((left, time + n));
                }
            }
            if !cooling.is_empty() && cooling[0].1 == time {
                heap.push(cooling.pop_front().unwrap().0);
            }
        }
        time
    }
}

    The Rust details worth a closer look:

    • Letters to indexes. A char converts to u8 with as for ASCII letters. b'A' is a byte literal, the u8 value 65, so task as u8 - b'A' is a number from 0 to 25. The final as usize turns it into a valid index.
    • Inferred types. count is an array of 26 numbers whose type Rust infers as i32, from how the counts are used with cooling. The heap holds those counts, so it is a max-heap of i32.
    • Iterating an array. for c in count goes over the array's values by value, which is allowed for arrays of numbers in edition 2021.
    • Tuples. The entries of cooling are (i32, i32) tuples. .0 is the first item and .1 the second.
    • VecDeque. It adds at the back with push_back and removes from the front with pop_front, both in constant time. Indexing it, as in cooling[0], reads the front without removing it.
    • unwrap(). pop() and pop_front() return an Option. Each call is guarded: the heap is known to be non-empty in the else branch, and the queue was just checked.
    • Last expression. time has no semicolon, so it is the function's value.

    Complexity

    Time: O(T log 26), where T is the number of tasks. Counting is O(T). Each copy of a task is popped from the heap once and pushed back at most once, and the heap never holds more than 26 counts, so each operation costs O(log 26). Idle stretches are skipped with one jump instead of one pass per unit, so a large cooldown does not slow the loop.

    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, AAABBB gives 6. A task is ready again in the very next unit, so nothing idles and the answer is the number of tasks.
    • One task kind. AAAAAA with n = 2 gives 16: six runs and five gaps of two idle units each, and no other task to fill them.
    • A single task. A with n = 100 gives 1. The cooldown only matters between copies, so no idle time is added at the end.
    • Two copies and a long cooldown. AA with n = 3 gives 5: A, three idle units, A.
    • Plenty of other tasks. ABCD with n = 5 gives 4: every task has one copy, so nothing needs to wait.
    • Largest input. 100,000 copies of A with n = 100 gives 10,099,900, which fits easily in an i32.
    • Counting idle units one at a time. It works, but it costs time proportional to the cooldown. The jump to the next ready time avoids that.
    • Running the task with the fewest copies. It leaves the big counts for the end, where they must idle. The heap must give the biggest count first.

    Testing

    • tasks = ['A','A','A','B','B','B'], n = 2 gives 8.
    • The same tasks with n = 0 give 6.
    • Six A and one each of B to G, with n = 2, give 16.
    • ['A'] with n = 100 gives 1.
    • ['A','A'] with n = 3 gives 5.
    • AAABBBCC with n = 2 gives 8, the number of tasks.
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free