Task Scheduler

Problem

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: 
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Constraints:

1 <= task.length <= 10⁴
tasks[i] is upper-case English letter.
The integer n is in the range [0, 100].

Solution

/**
 * @param {character[]} tasks
 * @param {number} n
 * @return {number}
 */
var leastInterval = function(tasks, n) {
    // frequency of each task
    let counter = {};
    for (const task of tasks) {
        if (!(task in counter)) {
            counter[task] = 0;
        }
        counter[task]++;
    }

    // heap to order tasks by frequency
    const maxHeap = new MaxPriorityQueue();
    for (const key in counter) {
        maxHeap.enqueue(counter[key]);
    }

    // compute min time required to finish all tasks
    let time = 0;
    const period = n + 1
    while (!maxHeap.isEmpty()) {
        const remain = [];
        let idle = 0;
        const tasks = maxHeap.size()
        time += period

        for (let i = 0; i <= n && !maxHeap.isEmpty(); i++) {
            remain.push(maxHeap.dequeue().element - 1);
        }

        for (const count of remain) {
            if (count) { // non-zero task count
                maxHeap.enqueue(count);
            }
        }

        if (maxHeap.isEmpty()) {
            time -= period - tasks
        }
    }
    return time;
};

We will implement a greedy solution. The main idea of our greedy algorithm is that we pick tasks to execute in the order of frequency. To do so, we first push all tasks into a max-heap maxHeap sorted by order of frequency. Next, we pop maxHeap at most n + 1 times for the tasks that we want to execute:

If there are >= n + 1 tasks in maxHeap, then there is no idle time, since n + 1 tasks enables us to not need to wait when repeating the first task in this chain.
Otherwise, if there are < n + 1 tasks in maxHeap, the idle time is the number of pops minus n + 1 (the only exception is the last chain when we're done executing all tasks).

We push all the tasks that are not finished back into maxHeap with their remaining count decremented by 1 (since we executed each task once), and repeat this entire process until all tasks are finished.

Problem​

Solution​

Problem

Solution