LeetCode 621中等贪心 · 计数
任务调度器 图解题解
这道题到底在问什么
给你一个由大写字母 A 到 Z 表示的任务列表 tasks，以及冷却时间 n。每个时间间隔可以完成一项任务或待命；两个相同任务之间必须间隔至少 n 个时间。返回完成所有任务所需的最短时间间隔。
- 输入
- tasks = ["A","A","A","B","B","B"], n = 2
- 输出
- 8
- 解释
- 一种序列是 A -＞ B -＞ idle -＞ A -＞ B -＞ idle -＞ A -＞ B。
- 输入
- tasks = ["A","C","A","B","D","B"], n = 1
- 输出
- 6
最优解：一步一步想明白
- 3很多人第一反应是套优先队列：每一轮把还没冷却的任务丢进大顶堆，弹出当前剩余次数最多的那个先做，再把它扔进冷却队列等 n 轮。这是教科书做法，能过，但要同时维护堆和冷却队列，代码长、边界多。
- 4转折：堆每轮总是优先消化最高频任务，所以最终排布一定是「最高频任务搭骨架，其余任务来填空」。既然结果形状固定，就不必真的跑堆，用计数一步算出长度。这就是本题从「堆模拟」简化成「贪心计数」的关键。
- 5counts = Counter(tasks).values()先只数任务种类和出现次数，原始顺序不重要。固定 8 格是为了后面摆最短时间轴。
- 6max_freq = max(counts)出现次数最多的任务最难安排，它决定冷却骨架要分几层。这里 A、B 都是 3 次。
- 7A _ _ A _ _ A3 个 A 之间各要隔 2 格，先摆出 A 空 空 A 空 空 A。中间的空位就是要填的冷却槽。
- 8max_count = 2B 也出现 3 次，和 A 并列。所以尾部那一层不只放 A，还得放 B，这就是公式末尾要加 max_count 的原因。
- 9A B idle A B idle A B样例一只有 A、B 两种任务，剩下的冷却空位没东西填，只能待命，于是冒出两个 idle。
- 10frame = (max_freq - 1) * (n + 1) + max_count前面 (max_freq-1) 个完整块，每块长度 n+1，也就是一个任务加 n 个槽；最后再补上 max_count 个尾巴任务。2×3+2 = 8。
- 11return max(len(tasks), frame)所有任务都得执行完，答案至少是 len(tasks)=6；而冷却骨架要求 8，更大，所以样例一返回 8。
- 12tasks = ["A","C","A","B","D","B"], n = 1换样例二：A、B 各 2 次，骨架只要 4，但还有 C、D 把空位填满了，不需要待命。此时 len=6 反而更大，答案就是 6。两个样例一对照，公式两端谁大取谁就清楚了。
- 15调度题的通用直觉：最高频元素常常决定答案的下界，其他元素只是用来塞进冷却空位。抓住这条，就不必背公式。
⚠️ 容易写错的地方
✗ 错：只返回 frame
✓ 对：返回 max(len(tasks), frame)
任务种类多到能填满空位时，真实时间是任务总数，frame 反而偏小。
✗ 错：max_count 忽略并列最高频
✓ 对：统计所有达到 max_freq 的任务数
A、B 同为最高频时，尾部那一层要放两个任务，少算就漏。
✗ 错：把一轮长度写成 n
✓ 对：一轮骨架长度是 n + 1
两个相同任务隔 n 个单位，加上任务本身一格，一块是 n+1。
完整代码（Python / C++ / Java）
Python
from collections import Counter
class Solution:
def leastInterval(self, tasks, n):
counts = Counter(tasks).values()
max_freq = max(counts)
max_count = sum(1 for c in counts if c == max_freq)
frame = (max_freq - 1) * (n + 1) + max_count
return max(len(tasks), frame)C++
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> cnt(26);
for (char c : tasks) cnt[c - 'A']++;
int max_freq = *max_element(cnt.begin(), cnt.end());
int max_count = count(cnt.begin(), cnt.end(), max_freq);
int frame = (max_freq - 1) * (n + 1) + max_count;
return max((int)tasks.size(), frame);
}
};Java
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] cnt = new int[26];
for (char c : tasks) cnt[c - 'A']++;
int max_freq = 0, max_count = 0;
for (int c : cnt) max_freq = Math.max(max_freq, c);
for (int c : cnt) if (c == max_freq) max_count++;
int frame = (max_freq - 1) * (n + 1) + max_count;
return Math.max(tasks.length, frame);
}
}套路模板（可背骨架 · 三语言）
# 「最高频搭骨架」三步模板：
# 1) 数频次 2) 取最高频与并列数 3) 骨架 vs 总数
cnt = 频次表(元素) # ① Counter / 数组
peak = max(cnt) # ② 最高频次数
ties = (cnt 中等于 peak 的个数) # ② 有几种并列最高
frame = (peak - 1) * (间隔 + 1) + ties # ③ 骨架长度
return max(总数, frame) # ③ 别忘和总数取大// 「最高频搭骨架」三步模板
int cnt[K] = {0}; // ① 频次表
for (auto x : 元素) cnt[idx(x)]++;
int peak = *max_element(cnt, cnt + K); // ② 最高频
int ties = count(cnt, cnt + K, peak); // ② 并列数
int frame = (peak - 1) * (间隔 + 1) + ties; // ③ 骨架
return max(总数, frame); // ③ 取大// 「最高频搭骨架」三步模板
int[] cnt = new int[K]; // ① 频次表
for (var x : 元素) cnt[idx(x)]++;
int peak = 0, ties = 0;
for (int c : cnt) peak = Math.max(peak, c); // ② 最高频
for (int c : cnt) if (c == peak) ties++; // ② 并列数
int frame = (peak - 1) * (间隔 + 1) + ties; // ③ 骨架
return Math.max(总数, frame); // ③ 取大复杂度
时间复杂度
O(m)
m 是任务总数，Counter 扫一遍统计频次；之后只对 26 个字母求 max 和计数，是常数。
空间复杂度
O(1)
只用一个长度 26 的计数数组，和任务数量无关。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 任务调度器 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果面试官要你用优先队列做，怎么写？+
每轮把未冷却的任务按剩余次数丢进大顶堆，弹出最多的先做，再压进一个冷却队列等 n 轮放回。能过但代码长，计数公式是它的等价简化。
公式里的 max_freq 和 max_count 各是什么？+
max_freq 是最高出现次数，决定骨架分几层；max_count 是有几种任务并列最高，决定最后一层放几个。
什么时候根本不会有 idle？+
当其他任务多到能填满所有冷却空位时，答案就退回任务总数 len(tasks)，一格 idle 都不需要。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。