621. 任务调度器">621. 任务调度器

621. 任务调度器

题目描述

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个相同种类的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

解题思路

首先，分析题型。题目的关键在于“两个任务之间的间隔至少为n”，那么总时长其实很大程度上取决于执行次数最多的的任务，以及怎么用其他任务尽可能地铺满间隔时间。“怎么铺满空余位置”是个技巧性的问题，因此可以归类为贪心的范畴，本题的难点就在于设计出最优的贪心策略。

我在做这道题的时候并没有想到很好的设计思路，只好尝试看懂官方的解法后把思路搬运过来。

为了说明上的方便，先定义下接下来要用到的常量：

设执行次数最多的任务一共执行了 maxExec 次
设执行次数最多的任务一共有 maxCount 种
设将要执行的任务总数是 numTasks

官方用一张表来描述任务执行的顺序，如下所示：
621. 任务调度器 - 图1

在该表中，执行次数最多的任务是 A 、B 、C ，最多执行了5次，即 maxCount = 3 ，maxExec = 5 。

表中的任务从左往右顺序执行，每行长度为 n + 1 ，刚好可以运行一轮任务。

上下相邻的任务执行间隔刚好为 n ，利用这一特性，我们可以竖着把同种类的任务铺在表上，没有铺满的地方就是CPU的空闲时间。以这种方式，我们可以把“CPU耗时最短的任务执行顺序”问题转化成了“怎么用其他任务尽可能铺满表的右半部分”。

在理想情况 n + 1 >= numTasks 下，我们可以奢侈地在每一列上只铺一种任务，表中的空间完全足够，而且多出来的空闲时间都不是多余的。此时的总执行时间为 (maxExec - 1) * (n + 1) + maxCount 。
在不理想情况 n + 1 < numTasks 下，铺任务的方式需要很高的技巧性，如下图所示。官方对这种构造方式的描述为：

一种构造的方法是，我们从倒数第二行开始，按照反向列优先的顺序（即先放入靠左侧的列，同一列中先放入下方的行），依次放入每一种任务，并且同一种任务需要连续地填入。

621. 任务调度器 - 图2

在上图中，表右侧的空出来的位置可以不计入统计，不把它当做空闲时间
也可以理解为，CPU跳过了右侧的空格子，另起一行开始执行
此时的总执行时间 = 任务总数 = numTasks

最后一点小技巧，

在理想情况下，由于空余位置总是存在，所以 (maxExec - 1) * (n + 1) + maxCount 一定大于等于 numTasks
而在不理想情况下，由于表宽超过了 n + 1 ，所以 (maxExec - 1) * (n + 1) + maxCount 一定小于 numTasks
因此只需要返回这两个数之间的最大值即可解决该题

复杂度分析

为了计算 maxExec 、maxCount ，需要建立哈希表来存储（任务，执行次数），然后遍历哈希表得到最多的执行次数，和对应的任务种类数目。

设任务种类数为 numTaskTypes ，任务总数为 numTasks 。

时间开销 = 建表（numTasks）+ 遍历获取最大值（numTaskTypes）+ 遍历获取符合条件的任务种类数（numTaskTypes）
= O( numTasks + numTaskTypes )

空间开销 = 哈希表的大小（numTaskTypes）= O( numTaskTypes )

知识点

贪心、桶思想、哈希表

代码

官方代码

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> freq;
        for (char ch: tasks) {
            ++freq[ch];
        }
        // 最多的执行次数
        int maxExec = max_element(freq.begin(), freq.end(), [](const auto& u, const auto& v) {
            return u.second < v.second;
        })->second;
        // 具有最多执行次数的任务数量
        int maxCount = accumulate(freq.begin(), freq.end(), 0, [=](int acc, const auto& u) {
            return acc + (u.second == maxExec);
        });
        return max((maxExec - 1) * (n + 1) + maxCount, static_cast<int>(tasks.size()));
    }
};

Leetcode题解

621. 任务调度器

621. 任务调度器

题目描述

解题思路

复杂度分析

知识点

代码

参考资料