LeetCode 621. 任务调度器

2025-06-16 HGNULB 约 6 分钟

文章信息 9 个分类 6 个标签

分类

题目描述

✅ 621. 任务调度器

题意分析

输入是一串用大写字母表示的任务和一个冷却值 n，要求输出「把全部任务做完最少需要多少个时间单位」。

时间被切成等长的单位格，每一格只能做一个任务或者待命。约束只有一条：同一种任务的两次执行之间，至少要隔开 n 个单位格。任务之间没有先后依赖，谁先做谁后做完全自由，所以这是一个安排顺序的问题，而不是选择做哪些任务的问题。

有两个信号值得注意。第一，任务只用大写字母标识，种类不超过 26 种，所以「按种类统计」的代价是常数。第二，题目只问总时长，不要求输出具体安排，说明答案很可能有闭式表达，不必真的把序列排出来。

边界上要考虑：n = 0 表示没有冷却，所有任务连着做即可；只有一种任务时，每两次执行之间都必须塞满待命；任务种类很多时，待命有可能一个都不需要。

解法：按最高频任务构造时间框架

核心思路

题目只问最短时间，不要求输出具体顺序，因此没必要用堆逐格模拟。真正决定待命数量的是最高频任务：它们最难被其他任务隔开。

设任务总数为 m，最高频次为 maxFreq，达到最高频次的任务种类数为 maxCount。先把这些最高频任务按轮摆放：

前 maxFreq - 1 轮后面都还要等待下一次同类任务，因此每轮至少占 n + 1 格；

最后一轮不需要再预留冷却，只需放下 maxCount 个最高频任务。

于是冷却约束给出的框架长度为
\[(maxFreq - 1) \times (n + 1) + maxCount\]
任务总数 m 也是下界，因为一个时间单位最多执行一个任务。因此答案至少是
\[\max\bigl(m,\ (maxFreq - 1) \times (n + 1) + maxCount\bigr)\]
还要说明这个下界一定可达。把每种最高频任务在每轮各放一次，其余任务每轮至多放一次：如果它们填不满框架，空位就是待命；如果任务多到溢出框架，就把各轮向右扩宽。扩宽只会增大同类任务的间距，不会破坏冷却限制，此时所有时间格都能放任务，总长就是 m。所以两个下界取较大值就是精确答案。

面试时可以把这个结论概括为：最高频任务决定最少需要多长的冷却框架，任务总数决定最少需要多少个执行格；填不满就待命，填得满就没有待命。

解题步骤

用长度为 26 的数组统计每种大写字母任务的出现次数，同时记录 maxFreq。

再扫描计数数组，统计有多少种任务的频次等于 maxFreq，得到 maxCount。必须在最大频次确定后再统计。

计算冷却框架 frame = (maxFreq - 1) * (n + 1) + maxCount。

返回 max(frame, tasks.length)。

以 tasks = ["A","A","A","B","B","B"]、n = 2 为例：maxFreq = 3，maxCount = 2，框架长度为 (3 - 1) * 3 + 2 = 8。一种最优安排是 A B 待命 A B 待命 A B，所以答案为 8。

再看无需待命的情况：tasks = ["A","A","A","B","B","B","C","C","D","D"]、n = 2。框架长度仍为 8，但任务总数为 10，可以安排成 A B C A B D A B C D。同类任务至少相隔 2 格，答案取任务总数 10。

代码实现

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(m)$，再次扫描固定的 26 个计数是 $O(1)$。

空间复杂度：$O(1)$。字符集固定为 26 个大写字母，计数数组不随输入规模增长。

关键点总结

公式中的 n + 1 是「一个任务格 + 后续 n 个冷却格」，不是只有冷却格数 n。

最后一轮之后无需冷却，所以只加 maxCount，不能再补一个完整周期。

maxCount 处理多个任务并列最高频的情况，例如 A、B 都出现 3 次时，最后一轮必须同时给 A、B 留位置。

frame 描述冷却造成的最短长度，tasks.length 描述任务本身占用的最短长度，最终必须取较大值。

公式不是记忆题。面试回答的重点是先给出两个下界，再解释「空位变待命、溢出则扩宽轮次」为何能构造出这个长度。

易错点总结

周期漏算任务格：写成 (maxFreq - 1) * n + maxCount。例如三个 A、n = 2 会误算为 5，正确答案是 7。

忽略并列最高频：把结尾写死为 1。AAABBB、n = 2 应为 8，而不是 7。

忘记与任务总数取最大值：任务足够多时没有待命，答案就是 tasks.length，不能返回更小的框架长度。

把最后一轮也算成完整周期：写成 maxFreq * (n + 1) 会多算末尾无需等待的冷却时间。

边统计边累计 maxCount：中途的最大值还会变化，容易保留过期计数；应先确定 maxFreq，再单独统计 maxCount。

相似题目

题目	难度	考察点
347. 前 K 个高频元素	中等	只做频次统计与选前 K，不涉及间隔约束
451. 根据字符出现频率排序	中等	按频次降序重排字符，输出序列而非长度
767. 重构字符串	中等	同样受最高频元素支配，但要判定可行并构造出具体排列
1405. 最长快乐字符串	中等	限制的是连续出现次数上限，需要逐位贪心而非闭式公式
630. 课程表 III	困难	带截止时间的任务选择，用堆做反悔贪心