50. Task Scheduler

MediumArray Hash Table Greedy Heap

A CPU has to run a list of tasks, each labelled with an uppercase letter A to Z. Every task takes exactly one time unit, and in each unit the CPU either runs one task or sits idle.

There is a cooling rule: two tasks with the same label must be separated by at least n units (filled with other tasks or idling). Tasks can be run in any order you like.

Return the minimum number of time units needed to finish every task.

Example 1

Input: tasks = ["X","X","X","Y","Y","Z"], n = 2
Output: 7

Explanation: One optimal schedule is X Y Z X Y idle X. The three Xs need two gaps of at least 2 units, and only one gap slot is left unfilled.

Example 2

Input: tasks = ["A","A","B","B"], n = 0
Output: 4

Explanation: With no cooldown the tasks can run back to back.

Example 3

Input: tasks = ["A","A","A","A","B","C"], n = 3
Output: 13

Explanation: A B C idle A idle idle idle A idle idle idle A: the four As dictate the length.

Constraints

1 <= tasks.length <= 10^4
tasks[i] is an uppercase English letter
0 <= n <= 100

💡 Hint 1

Only the counts matter, not the order of the input. Which task constrains the schedule the most?

💡 Hint 2

Lay out the most frequent task (count f) first: it creates f - 1 frames of length n + 1, followed by a final partial frame.

💡 Hint 3

The final frame holds every task tied for the top count. If there are more tasks than frame slots, no idling is needed at all and the answer is simply tasks.length.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Count each label. Let f be the highest count and m the number of labels that reach it. Schedule the most frequent task first: its f copies need f - 1 frames of n + 1 units each (one copy plus n cooling slots), then a last frame holding the m tasks tied at the top, for (f - 1) · (n + 1) + m units. Every other task fits into the cooling slots, because each has fewer than f copies and so never collides with itself. If the slots overflow, the schedule simply stretches with no idling at all, and its length is tasks.length. The answer is the larger of the two. (Simulating with a max-heap of counts and a cooldown queue gives the same result in O(n log 26).)

Time O(n)Space O(1) (26 counters)

function leastInterval(tasks, n) {
  const count = new Array(26).fill(0);
  for (const t of tasks) count[t.charCodeAt(0) - 65]++;
  const maxFreq = Math.max(...count);
  const tiedAtMax = count.filter((c) => c === maxFreq).length;
  return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + tiedAtMax);
}

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        int maxFreq = 0;
        for (char t : tasks) maxFreq = Math.max(maxFreq, ++count[t - 'A']);
        int tiedAtMax = 0;
        for (int c : count) if (c == maxFreq) tiedAtMax++;
        return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + tiedAtMax);
    }
}

/**
 * @param {string[]} tasks one-character strings "A".."Z"
 * @param {number} n
 * @return {number}
 */
function leastInterval(tasks, n) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit