.jpg)
678 字
3 分钟
任务调度器
题目描述
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个 相同种类 的任务之间必须有长度为 n 的冷却时间。
返回完成所有任务所需要的 最短时间间隔 。
解题思路
- 频率统计：计算每个任务出现的频率，找出最高频率
maxFreq及其任务数countMax - 框架计算：核心时间框架为
(maxFreq - 1) × (n + 1) + countMax(maxFreq - 1)个完整周期- 每个周期长度
n + 1（任务 + 冷却） - 最后添加最高频任务数
countMax
- 边界处理：当任务种类丰富时，实际时间取
max(框架值, 任务总数)- 冷却间隔可被其他任务填满时无需额外待命
- 冷却机制：通过公式自动满足相同任务间隔要求
关键洞察
- 频率瓶颈原理：最高频任务决定时间下限，其执行间隔形成基本框架
- 冷却槽位复用：非高频任务可填充冷却间隔，减少待命时间
- 多峰值处理：多个最高频任务需在末尾连续执行（
+countMax） - 自平衡特性：当任务种类 > 冷却槽位时，总时间 = 任务总数
- 常数空间优化：仅需频率统计，无需模拟调度过程
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(N)：遍历任务列表统计频率 O(N)，查找最高频 O(1)（任务种类上限 26） |
| 空间复杂度 | O(1)：使用固定大小数组（长度 26）统计频率，与输入规模无关 |
代码实现
/** * @link {https://leetcode.cn/problems/task-scheduler/} * @param {character[]} tasks - 任务列表，每个任务用大写字母表示 * @param {number} n - 相同任务之间的最小间隔 * @return {number} - 完成所有任务所需的最短时间 */const leastInterval = (tasks, n) => { // 统计任务频率（A-Z 映射到 0-25） const freq = Array(26).fill(0); for (const t of tasks) { freq[t.charCodeAt(0) - 65]++; // 'A' ASCII 65 }
// 找出最高频率及出现次数 const maxFreq = Math.max(...freq); const countMax = freq.filter(f => f === maxFreq).length;
// 计算最短时间 return Math.max( (maxFreq - 1) * (n + 1) + countMax, tasks.length );};最短时间 = max( (maxFreq - 1) × (冷却间隔 + 1) + 峰值任务数, // 理论框架值 任务总数 // 实际最小时间 )