621. Task Scheduler

At a Glance

• Topic: Array
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 621

Problem Statement

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = ["A","C","A","B","D","B"], n = 1

Output: 6

Explanation: A possible s...

Approach & Solution Steps

• Simulation — max-heap of counts, each cycle pick best available, cooldown queue — models process — O(total time) with heap log 26.
• Math — arrange (maxFreq-1) blocks of length (n+1) then append tail of max-frequency symbols — O(26) time, O(1) space — preferred when explained.

Optimal JS Solution

function leastInterval(tasks, cooldown) {
  const freq = new Map();
  for (const label of tasks) {
    freq.set(label, (freq.get(label) ?? 0) + 1);
  }
  let maxFreq = 0;
  for (const count of freq.values()) {
    maxFreq = Math.max(maxFreq, count);
  }
  let numWithMaxFreq = 0;
  for (const count of freq.values()) {
    if (count === maxFreq) {
      numWithMaxFreq += 1;
    }
  }
  const minSlots = (maxFreq - 1) * (cooldown + 1) + numWithMaxFreq;
  return Math.max(tasks.length, minSlots);
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.