Overview

Given a list of tasks represented by characters and a non-negative cooldown interval n, find the minimum number of intervals (time units) the CPU needs to finish all tasks.

Each task takes one unit of time. Between two same tasks, there must be at least n units of cooldown. During cooldown, the CPU can execute different tasks or remain idle.

Constraints

• 1 <= tasks.length <= 10,000
• tasks[i] is an uppercase English letter.
• 0 <= n <= 100

Examples

leastInterval(["A","A","A","B","B","B"], 2);
// => 8  (A B idle A B idle A B)

leastInterval(["A","A","A","B","B","B"], 0);
// => 6  (no cooldown needed)

leastInterval(["A","A","A","A","A","A","B","C","D","E","F","G"], 2);
// => 16

Solution

function leastInterval(tasks, n) {
  const freq = {};
  for (const t of tasks) freq[t] = (freq[t] || 0) + 1;

  const maxFreq = Math.max(...Object.values(freq));
  const maxCount = Object.values(freq).filter(f => f === maxFreq).length;

  // (maxFreq - 1) full rounds of (n + 1) slots, plus the last partial round
  const result = (maxFreq - 1) * (n + 1) + maxCount;

  // Can never be less than total tasks
  return Math.max(result, tasks.length);
}

Resources

• Task Scheduler — LeetCode
• Greedy Algorithm — Wikipedia