Start learning free

LESSON 391 OF 540 · HEAP

Task Scheduler in Kotlin: O(T log 26) with a 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

    KOTLIN · HEAP

    Task Scheduler in Kotlin, explained

    Problem overview

    The function leastInterval(tasks: CharArray, n: Int): Int receives a list of tasks, each an uppercase letter from A to Z, where equal letters are copies of the same task. Running one task takes one unit of time, and in every unit the CPU either runs one task or idles. After a task runs, the CPU needs n other units (other tasks or idle ones) before it can run that same task again. The tasks can run in any order, and the function returns the fewest units needed to run all of them.

    For tasks = A A A B B B and n = 2 the answer is 8. One best order is A B idle A B idle A B. Two kinds of task can't fill the gaps between copies, so the CPU idles twice. With n = 0 there is no cooldown, any order works, and the answer is 6. For six A's, one each of B to G, and n = 2, the answer is 16: the six A's force a gap pattern, the other tasks fill the first gaps, and the CPU idles in the rest.

    The lesson 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

    The names of the tasks don't matter, only how many copies each has. The idea is to simulate the CPU one unit at a time with a greedy rule: run the task with the most copies left. Tasks with many copies need the most room between their runs, so starting them early leaves the fewest idle units at the end.

    Two structures support the simulation:

    • A max-heap of counts holds the tasks that are ready to run. The biggest count is on top. The heap never holds more than 26 entries, one per letter, so each operation costs O(log 26).
    • A queue named cooling holds tasks that just ran and are waiting out their cooldown. Each entry is intArrayOf(left, readyTime): the copies left and the time unit at whose end the cooldown is over. Tasks enter the queue in the order they run, so they also become ready in that order, and the front is always the next one to return.

    When the heap is empty but tasks are still cooling, the CPU can only idle. Rather than count idle units one by one, the simulation jumps the clock to the moment the first waiting task is ready. This keeps the work proportional to the number of tasks, not to the idle time.

    A short counting formula also exists: if the most frequent task appears m times and c tasks appear that often, the answer is the bigger of tasks.size and (m - 1) * (n + 1) + c. This lesson builds the simulation, which also shows why the formula holds.

    Step by step

    1. Count the copies. Create count as IntArray(26), one place per letter, filled with zeros.
    2. Loop over tasks, naming each one task.
    3. Add one to the letter's count at index task - 'A'. Subtracting 'A' turns A into 0, B into 1, up to Z as 25.
    4. Create the heap, a PriorityQueue<Int> with compareByDescending { it }, so the biggest count comes out first.
    5. Loop over count, naming each count c.
    6. Add only the non-zero counts to the heap. Letters that never appear have nothing to run.
    7. Create cooling as an empty ArrayDeque<IntArray>().
    8. Start time at 0. It counts the units used so far, and it is the answer at the end.
    9. Loop while heap.isNotEmpty() || cooling.isNotEmpty(). The work is done only when nothing is ready and nothing is cooling.
    10. Start a new unit with time++.
    11. If the heap is empty, no task can run, so set time to the ready time of the front of cooling, cooling.first()[1]. This counts all the idle units in one step.
    12. Otherwise run a task: heap.poll() - 1 is the number of copies it has left after this run.
    13. If copies remain, add intArrayOf(left, time + n) at the back of cooling. A task that ran at time can run again at time + n + 1, after n other units. A task with no copies left is done and isn't queued.
    14. Release a ready task. If the front of cooling has a ready time equal to time, remove it and put its remaining count back into the heap.
    15. Return time, the unit in which the last task ran.

    The solution in Kotlin

    class Solution {
    fun leastInterval(tasks: CharArray, n: Int): Int {
        val count = IntArray(26)
        for (task in tasks) {
            count[task - 'A']++
        }
        val heap = PriorityQueue<Int>(compareByDescending { it })
        for (c in count) {
            if (c > 0) {
                heap.add(c)
            }
        }
        val cooling = ArrayDeque<IntArray>()
        var time = 0
        while (heap.isNotEmpty() || cooling.isNotEmpty()) {
            time++
            if (heap.isEmpty()) {
                time = cooling.first()[1]
            } else {
                val left = heap.poll() - 1
                if (left > 0) {
                    cooling.addLast(intArrayOf(left, time + n))
                }
            }
            if (cooling.isNotEmpty() && cooling.first()[1] == time) {
                heap.add(cooling.removeFirst()[0])
            }
        }
        return time
    }
}

    Kotlin details worth a look:

    • Character arithmetic. Subtracting one Char from another gives an Int, so task - 'A' is a valid array index: 'C' - 'A' is 2. Adding an Int to a Char gives a Char, but subtracting two Chars gives the distance between them.
    • count[...]++. Kotlin allows ++ on an array element, which reads it, adds one and writes it back.
    • Java's heap, Kotlin's queue. PriorityQueue is java.util.PriorityQueue, a min-heap by default, and compareByDescending { it } reverses it for counts. ArrayDeque is Kotlin's own, in kotlin.collections, so it needs no import. In a file of your own, add import java.util.PriorityQueue.
    • Deque functions. addLast adds at the back, and first() and removeFirst() read and remove the front. Calling them on an empty deque throws NoSuchElementException, which is why each use is guarded by an emptiness check or by the loop condition.
    • poll returns a nullable type. heap.poll() comes from Java and has the platform type Int!, so heap.poll() - 1 compiles. It is safe because the else branch only runs when the heap is not empty.
    • Short-circuit &&. In cooling.isNotEmpty() && cooling.first()[1] == time, the right side runs only when the deque has an element.
    • time is a var. It is incremented and also assigned, when the clock jumps.

    Complexity

    Time: O(T log 26). Counting is O(T). Each loop turn runs one task, and every task copy runs exactly once, so there are T turns. Each turn does a heap removal and at most one heap insertion, both O(log 26) because the heap holds at most 26 counts. Idle stretches are skipped by one assignment, not by looping.

    Space: O(1). The count array has 26 places. The heap and the queue together hold at most 26 letters, because a letter is in exactly one of them or finished.

    Edge cases and common mistakes

    • No cooldown. With n = 0 a task is ready again immediately, so the answer is tasks.size. A A A B B B gives 6.
    • One kind of task. A A with n = 100 gives 102: the first A runs at unit 1, the CPU idles for 100 units, and the second A runs at unit 102. The clock jumps over the idle stretch in one step.
    • A cooldown that's never needed. A B C with n = 5 gives 3. No letter repeats, so nothing waits.
    • A single task. A with n = 100 gives 1: after the last copy there is no reason to wait.
    • Queuing finished tasks. A task with no copies left must not go into cooling, or the loop would wait for something that doesn't exist.
    • Off-by-one on the cooldown. A task that ran at time needs n other units, so it returns at time + n + 1. The code stores time + n, the unit at whose end the cooldown is over, and the next turn increments time before running.
    • Running the smallest count first. A min-heap would leave the biggest group for last and add idle units that a better order avoids.

    Testing

    Trace for A A A B B B with n = 2:

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

    Units 1 and 2 run A and B, and unit 3 is idle: both tasks are still cooling, so the heap is empty. Units 4 and 5 run them again, unit 6 is idle, and units 7 and 8 run the last copies. The total is 8.

    Trace for A A with n = 100:

    time=1: run a task with 2 copies, 1 left
time=101: idle until time 101, ready again with 1 left
time=102: run a task with 1 copies, 0 left

    Here the clock goes from 1 to 101 in one step, then the last copy runs at unit 102.

    • A A A B B B, n = 2 gives 8.
    • A A A B B B, n = 0 gives 6.
    • Six A's and one each of B, C, D, E, F, G, with n = 2 gives 16.
    • A, n = 100 gives 1.
    • A B C, n = 5 gives 3.
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free