LeetCode 621. 任务调度器

◎

本节目标

由最高频任务构造冷却调度骨架，并与任务总数下界取最大值。

这是贪心综合中调度骨架的拓展题。

题意与约束

同类任务之间至少间隔 n 个时间单位；每个时间单位执行一个任务或空闲。求完成全部任务的最短时间。

直接思路与瓶颈

逐时刻选择当前剩余最多的任务可以模拟，但需要维护冷却队列，且不容易一眼得到最优时间。真正决定空闲下界的是最高频任务。

贪心模型与算法推导

设最高频次为 maxFrequency，达到该频次的任务种类数为 maxCount。它们构成 (maxFrequency-1) 个长度 n+1 的间隔，再加最后一组最高频任务，骨架给出下界 (maxFrequency-1)*(n+1)+maxCount。任务总数也给出下界，答案取这两个下界的最大值。

正确性依据

任一最高频任务的相邻出现必须隔开 n 个位置，因此骨架给出不可突破的下界；其余任务尽量填入间隙。若任务足够多，所有间隙被填满，日程不能短于任务总数；若不足，剩余位置必须空闲。两种下界取最大恰为可构造的最短时间。

样例执行过程

A,A,A,B,B,B 且 n=2 可排成 A B idle A B idle A B，骨架为 (3-1)*(2+1)+2=8。若加入足够多其他任务，间隙会被填满，此时答案应回到任务总数而不是骨架长度。

代码实现

C++

C++17

#include <algorithm>
#include <array>
#include <vector>
using namespace std;

class Solution {
public:
    int leastInterval(vector<char> tasks, int n) {
        array<int, 26> frequency{};
        for (char task : tasks) frequency[task - 'A']++;
        const int maxFrequency = *max_element(frequency.begin(), frequency.end());
        const int maxCount = count(frequency.begin(), frequency.end(), maxFrequency);
        const int skeleton = (maxFrequency - 1) * (n + 1) + maxCount;
        return max(static_cast<int>(tasks.size()), skeleton);
    }
};

Python

Python 3

from collections import Counter


class Solution:
    def leastInterval(self, tasks: list[str], n: int) -> int:
        frequency = Counter(tasks)
        max_frequency = max(frequency.values())
        max_count = sum(count == max_frequency for count in frequency.values())
        skeleton = (max_frequency - 1) * (n + 1) + max_count
        return max(len(tasks), skeleton)

复杂度分析

统计 26 类大写字母，时间 O(m)，额外空间 O(1)，其中 m 为任务数。

边界与易错点

• n=0 时答案就是任务数。
• 最高频任务可能有多个，骨架末尾要加 maxCount。
• 不能只返回骨架下界：其他任务足够多时，任务总数下界会更大。

模式迁移

带冷却时间的重复任务调度，先寻找最紧约束的高频任务形成下界，再判断其余任务能否填满间隙。