任务调度器 图解题解

这道题的约束到底卡在哪

任务不限执行顺序、每个占一个时间单位，唯一的约束是同种任务两次执行之间至少隔 n 个单位；轮到没任务可干时只能插 idle 待命，而 idle 同样计入总时长。所以题目本质是排布问题：怎么安排才能让被迫空转的格子最少。直觉上，出现次数最多的任务是麻烦制造者——它和自己的冷却冲突次数最多，别的任务反而好办。

为什么最高频任务决定了骨架

盯住出现次数最多的任务，设它出现 maxCount 次。相邻两次之间至少隔 n 格，连它自己占的那一格算上，一个最小重复周期就是 n + 1 格——这也回答了「周期为什么是 n + 1 而不是 n」。前 maxCount - 1 次执行各自撑起一个完整周期，共 (maxCount - 1) × (n + 1) 格；最后一次执行完不必再等冷却，此时有几个任务并列最高频，末尾就各占一格，再加 maxTasks。这两截拼起来就是骨架长度，其余低频任务只负责往周期的空隙里填。

为什么还要和任务总数取较大值

骨架公式隐含一个假设：周期里的空隙填不满，需要 idle 补位。但任务种类足够多时，空隙全被占满之后还有剩余任务——把它们插进各个周期也不违反间隔约束，因为周期被撑得更宽，同种任务的间距只会更充裕。这种情况下一格 idle 都不需要，总时长就等于任务总数本身，骨架公式反而算少了。所以最终答案是 max(骨架, len(tasks))，漏掉这一步兜底是本题最常见的错。

贪心每轮挑剩余最多的为什么对

若用模拟来验证：每一轮的 n + 1 格里，从剩余次数最多的任务开始挑着放，放不满就 idle。优先消耗高频任务，是为了防止它们攒到最后挤成一团、只能靠大量空转硬隔开——先把最难安置的摊开，容易的自然见缝插针。用最大堆模拟这个贪心过程，答案与公式一致，公式正是对该过程的数学闭式。以示例 A、B 各 6 次，C 4 次，D、E 各 2 次，n 取 2 为例：骨架 (6 - 1) × 3 + 2 得 17，任务总数 20，取大为 20。

复杂度与容易翻车的细节

统计频次只需扫一遍任务表，时间 O(N)；任务种类至多 26 个字母，计数数组是常数空间 O(1)。三个细节最容易错：并列最高频的任务必须全部计入 maxTasks，只算一个会把末轮算短；周期长度是 n + 1 不是 n；忘了与任务总数取 max。另外公式解只给最短时长、不输出具体排班，若面试官追问执行序列，再补最大堆逐轮模拟即可。

Python

from collections import Counter
def leastInterval(tasks, n):
    cnt = Counter(tasks)
    maxCount = max(cnt.values())
    # 有多少个任务并列最高频
    maxTasks = sum(1 for v in cnt.values() if v == maxCount)
    # 骨架长度 与 任务总数 取较大者
    return max((maxCount - 1) * (n + 1) + maxTasks, len(tasks))

C++

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int cnt[26] = {0};
        for (char c : tasks) cnt[c - 'A']++;
        int maxCount = *max_element(cnt, cnt + 26);
        int maxTasks = count(cnt, cnt + 26, maxCount);
        int skeleton = (maxCount - 1) * (n + 1) + maxTasks;
        return max(skeleton, (int)tasks.size());
    }
};

Java

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] cnt = new int[26];
        for (char c : tasks) cnt[c - 'A']++;
        int maxCount = 0;
        for (int v : cnt) maxCount = Math.max(maxCount, v);
        int maxTasks = 0;
        for (int v : cnt) if (v == maxCount) maxTasks++;
        int skeleton = (maxCount - 1) * (n + 1) + maxTasks;
        return Math.max(skeleton, tasks.length);
    }
}