LeetCode 621. 任务调度器
题目描述
题意分析
每个任务占一个时间单位，任务顺序可以重排。两次执行相同种类的任务之间，必须放下至少
n个其他任务或待命位置，也就是两次执行的位置至少相差n+1。求完成全部任务的最短时间，只需计算长度。
解法：按最高频任务构造时间框架
核心思路
[!blue]
设任务总数为
m，最大频次为maxFreq，达到这个频次的种类数为maxCount。总时间显然不能少于m；重复最多的任务还会给出另一个下界。在这
maxCount种任务中，第一次执行最晚的那一种，首次出现不会早于第maxCount个时间单位。它还要再执行maxFreq-1次，每两次至少相隔n+1，因此完成时间至少为(maxFreq-1)*(n+1)+maxCount，记作frame。这两个下界的较大值可以通过轮次安排达到：前
maxFreq-1轮各放一次所有最高频任务，最后一轮再按同样顺序各放一次。前面的轮次至少保留n+1个位置，最后一轮只有maxCount个任务，结束后不必继续冷却。其余种类最多出现
maxFreq-1次，可以分散到前面的轮次中。具体地，先分配需要占满每一轮的种类，再逐种把剩余任务按轮次循环填入，使各轮长度最多相差 1。同种任务在相邻轮的位置相同；若分配绕回第一轮，由于该种类没有占满所有轮，两段之间至少有一轮不含它，因此也能保持冷却间隔。每轮不足
n+1的部分用待命补足。任务少时，总长度正好是frame；任务多到超过这些位置时，各轮都已填满，扩展后的间隔只会更长，无需待命，总长度就是m。所以最优答案为max(m, frame)。若maxFreq=1，所有任务都不同，直接执行完即可，这个公式仍返回m。
解题步骤
- 用长度为 26 的数组统计每种大写字母的次数，同时求出
maxFreq。- 频次统计完成后，再扫描频次数组，计算有多少种任务达到
maxFreq，得到maxCount。- 计算
frame = (maxFreq-1)*(n+1)+maxCount。- 返回
frame与任务总数的较大者；不需要实际模拟上述轮次或保存任务顺序。
n=0时相同任务可以连续执行，公式返回任务数；只有一种任务时，只能在相邻两次执行之间待命，公式正好保留这maxFreq-1段冷却时间。
代码实现
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
int maxFreq = 0;
for (char task : tasks) {
freq[task - 'A']++;
maxFreq = Math.max(maxFreq, freq[task - 'A']);
}
// 统计最终最大频次对应的任务种类数
int maxCount = 0;
for (int count : freq) {
if (count == maxFreq) {
maxCount++;
}
}
// 最后一轮只放并列最多的任务，不再补尾部冷却
int frame = (maxFreq - 1) * (n + 1) + maxCount;
return Math.max(frame, tasks.length);
}
}
func leastInterval(tasks []byte, n int) int {
freq := make([]int, 26)
maxFreq := 0
for _, task := range tasks {
idx := int(task - 'A')
freq[idx]++
if freq[idx] > maxFreq {
maxFreq = freq[idx]
}
}
// 统计最终最大频次对应的任务种类数
maxCount := 0
for _, count := range freq {
if count == maxFreq {
maxCount++
}
}
// 最后一轮只放并列最多的任务，不再补尾部冷却
frame := (maxFreq-1)*(n+1) + maxCount
if frame > len(tasks) {
return frame
}
return len(tasks)
}
复杂度分析
- 时间复杂度：$O(m)$，
m为任务总数，字母表扫描为常数。- 空间复杂度：$O(1)$，固定频次表。
关键点总结
[!green]
maxCount是并列最多的种类数，不是任务总次数。n是中间必须隔开的数量，两次执行位置的差应为n+1。- 最高频任务决定必要的轮次数，其他任务优先占用本来需要待命的位置。
- 两个下界都必须满足，最后一轮之后不再计算冷却时间。
易错点总结
[!yellow]
- 只返回框架长度，任务过多时可能少于实际任务数。
- 框架使用
maxFreq轮完整间隔，会多算末尾待命。- 最大频次改变后仍累计旧的并列数量，会算错尾轮规模。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 358. K 距离间隔重排字符串 | 困难 | 同样限制相同任务或字符间的距离，原题构造字符串且不允许空闲，本题可插入空闲并最小化总长度。 |
| 767. 重构字符串 | 中等 | 相同字符不能相邻是冷却间隔为1的相近约束，本题还允许等待时隙。 |