Task Scheduler（任务调度器）

题目 / Problem

中文： 给定一个 CPU 任务数组 tasks，每个任务用大写字母 A-Z 表示，并给定冷却时间 n。

每个 CPU 时间单位可以执行一个任务，也可以处于空闲状态。任务可以按任意顺序执行，但两个相同类型的任务之间必须至少间隔 n 个时间单位。

返回完成所有任务所需的最少 CPU 时间单位数。

English: Given an array of CPU tasks labeled with uppercase letters A-Z and a cooldown value n, each CPU interval may execute one task or remain idle.

Tasks may be completed in any order, but two tasks with the same label must have at least n intervals between them.

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

示例 / Examples

Example 1

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

一种最优安排为：
One optimal schedule is:

A → B → idle → A → B → idle → A → B

相同任务之间都有至少两个时间单位。
Every pair of equal tasks is separated by at least two intervals.

Example 2

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

A → B → C → D → A → B

所有位置都可以放入实际任务，不需要空闲时间。
Every interval can contain a real task, so no idle time is needed.

Example 3

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

A → B → idle → idle → A → B → idle → idle → A → B

任务类型只有 A 和 B，无法填满长度为 3 的冷却间隔，因此需要空闲时间。
Only task types A and B are available, so they cannot completely fill the cooldown gaps and idle intervals are required.

约束 / Constraints

• 1 <= tasks.length <= 10^4
• tasks[i] 是大写英文字母。
  Each tasks[i] is an uppercase English letter.
• 0 <= n <= 100

核心观察：最高频任务决定框架 / Key Observation: Most Frequent Tasks Define the Frame

出现次数最多的任务最难安排，因为它需要最多的冷却间隔。设：
The most frequent task is the hardest to schedule because it requires the greatest number of cooldown gaps. Let:

maxFrequency = 任一任务的最大出现次数
               maximum frequency of any task

假设最高频任务为 A，出现 3 次，冷却时间 n = 2。先摆放 A：
Suppose the most frequent task is A, appearing three times with n = 2. Place the As first:

A _ _ | A _ _ | A

前三个 A 之间形成 maxFrequency - 1 个完整间隔。每个间隔连同开头的 A，构成长度为 n + 1 的区块：
The first maxFrequency - 1 occurrences create full gaps. Each gap together with its leading A forms a block of length n + 1:

(maxFrequency - 1) × (n + 1)

最后再加上末尾的最高频任务。
The final occurrence is added at the end.

多个任务具有相同最高频率 / Multiple Tasks Share the Maximum Frequency

如果 A 和 B 都出现 3 次，则最后一组不只有一个任务：
If both A and B appear three times, the final group contains more than one task:

A B _ | A B _ | A B

设：
Let:

maxCount = 出现次数等于 maxFrequency 的任务类型数量
           number of task types whose frequency equals maxFrequency

由最高频任务构成的最小框架长度为：
The minimum frame length imposed by the most frequent tasks is:

(maxFrequency - 1) × (n + 1) + maxCount

最终公式 / Final Formula

其他低频任务可以用来填充框架中的空位：
Less frequent tasks can fill empty positions inside the frame:

• 如果任务足够多，所有空位都会被填满，结果至少是 tasks.length。
  If enough tasks exist, every gap is filled and the result is at least tasks.length.
• 如果任务不够，剩余位置必须由 idle 填充，结果由框架长度决定。
  If there are too few tasks, remaining positions must be idle and the frame length determines the result.

因此：
Therefore:

answer = max(
  tasks.length,
  (maxFrequency - 1) × (n + 1) + maxCount
)

JavaScript 实现 / JavaScript Implementation

/**
 * @param {character[]} tasks
 * @param {number} n
 * @return {number}
 */
function leastInterval(tasks, n) {
  const frequencies = new Array(26).fill(0);

  for (const task of tasks) {
    const index = task.charCodeAt(0) - 65;
    frequencies[index]++;
  }

  let maxFrequency = 0;

  for (const frequency of frequencies) {
    maxFrequency = Math.max(maxFrequency, frequency);
  }

  let maxCount = 0;

  for (const frequency of frequencies) {
    if (frequency === maxFrequency) {
      maxCount++;
    }
  }

  const frameLength =
    (maxFrequency - 1) * (n + 1) + maxCount;

  return Math.max(tasks.length, frameLength);
}

执行过程 / Walkthrough

Example 1

tasks = [A,A,A,B,B,B]
n = 2

maxFrequency = 3
maxCount = 2  // A 和 B / A and B

框架长度：
Frame length:

(3 - 1) × (2 + 1) + 2
= 2 × 3 + 2
= 8

tasks.length = 6
answer = max(6, 8) = 8

Example 2

tasks = [A,C,A,B,D,B]
n = 1

maxFrequency = 2
maxCount = 2  // A 和 B / A and B

frameLength = (2 - 1) × (1 + 1) + 2 = 4
tasks.length = 6
answer = max(6, 4) = 6

框架给出的下界只有 4，但实际有 6 个任务需要执行，因此答案是 6。其他任务足以填满所有冷却位置。
The frame lower bound is only 4, but six tasks must actually be executed, so the answer is 6. Other tasks fill all cooldown positions.

Example 3

maxFrequency = 3
maxCount = 2
n = 3

frameLength = (3 - 1) × (3 + 1) + 2 = 10
answer = max(6, 10) = 10

为什么只看最高频率就足够？ / Why Is the Maximum Frequency Sufficient?

最高频任务产生最严格的间隔要求。只要围绕它们构造的框架合法，其他出现次数更少的任务就可以尽量放入框架空位。
The most frequent tasks impose the strictest spacing requirement. Once a valid frame is built around them, less frequent tasks can be placed into its empty positions.

如果其他任务多到超过所有空位，调度中就不会出现空闲时间，此时总长度正好等于任务总数。
If other tasks exceed the available gaps, the schedule contains no idle intervals and its total length equals the number of tasks.

所以答案是“最高频框架长度”和“任务总数”中的较大者。
That is why the answer is the larger of the most-frequent-task frame and the total task count.

特殊情况 / Edge Cases

n === 0

相同任务之间不需要等待，可以连续执行所有任务：
No cooldown is required, so all tasks may execute consecutively:

answer = tasks.length

公式也会自然得到这个结果。
The formula naturally produces this result as well.

所有任务都不同 / All Tasks Are Different

maxFrequency = 1
maxCount = tasks.length

frameLength = 0 × (n + 1) + tasks.length
            = tasks.length

不需要任何空闲时间。
No idle intervals are needed.

另一种方法：最大堆模拟 / Alternative: Max-Heap Simulation

也可以使用最大堆，每轮最多选择 n + 1 个当前剩余次数最多且互不相同的任务，再把尚未完成的任务放回堆中。
A max heap can simulate the schedule by selecting up to n + 1 currently most frequent distinct tasks per round, then reinserting unfinished tasks.

堆模拟更容易扩展到需要返回具体调度顺序的情况，但本题只要求最短时间，计数公式更简单、空间更少。
Heap simulation is easier to extend when an actual schedule must be returned, but the counting formula is simpler and uses less space when only the minimum length is required.

复杂度 / Complexity

• 时间复杂度 / Time: O(tasks.length)，统计任务频率需要线性时间，遍历固定的 26 个频率为常数时间。
  Counting task frequencies is linear, and scanning the fixed 26 entries is constant time.
• 空间复杂度 / Space: O(1)，频率数组长度固定为 26。
  The frequency array always has length 26.

易错点 / Common Pitfalls

• 冷却时间 n 表示两个相同任务之间至少有 n 个时间单位，因此区块长度是 n + 1。
  A cooldown of n means at least n intervals between equal tasks, so each frame block has length n + 1.
• 框架只包含 maxFrequency - 1 个完整区块，最后一组任务单独计算。
  The frame contains only maxFrequency - 1 complete blocks; the final task group is counted separately.
• 必须统计有多少种任务达到最高频率，即 maxCount。
  Count how many task types share the maximum frequency as maxCount.
• 最终要取 Math.max(tasks.length, frameLength)，不能只返回框架长度。
  Return Math.max(tasks.length, frameLength), not the frame length alone.
• 不需要真的构造包含 idle 的调度序列。
  There is no need to construct the actual schedule containing idle intervals.
• 字符是大写字母，因此字符编码映射使用 'A' 的编码 65。
  Tasks are uppercase letters, so character-code indexing subtracts 65, the code for 'A'.