Leetcode 621.任务调度器

题目描述：

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

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

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

示例 1：

1
2
3
4

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 

示例 2：

1
2
3
4
5
6
7
8

输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
诸如此类

示例 3：

1
2
3
4

输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
     A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

提示：

• $1 <= task.length <= 10^4$
• tasks[i] 是大写英文字母
• n 的取值范围为 [0, 100]

链接：

https://leetcode-cn.com/problems/task-scheduler

题目分析

  我们最先想到的应该是贪心的做法，也就是任务量最多的任务先完成。而执行一个任务之后都要等待 n 时间过后才能继续该任务，那么我们可以将 n+1 时间视为一个执行周期。假设任务量最多的任务次数是 maxtimes，那么我们至少就需要 maxtimes 个执行周期。假设任务数最多的任务是 A，需要执行 6 次，等待时间 n=2。那么我们的执行示意图就如下图所示。当然最后一个执行周期执行完 A 就可以结束了。总时间是 (2+1)*(6-1)+1=16

  然后我们就可以对每个执行周期中的其他空位继续填入其他任务，我们先假设任务的总量可以安排到这些执行周期内。可以看到任务 B 执行次数跟 A 一样都是最大值，需要排到最后一个执行周期。而任务 C 是不会对结果有任何影响的。总时间是 (2+1)*(6-1)+2=17。这个时候即使将 C 下面的三个“等待”时间填满也可以。

  假设任务量最多的任务共有 diff 种，那么假设总的任务量没有超过 (n+1)*(maxtimes-1)+diff 时，我们肯定是能够按照这种方法将其安排进这些任务列表里的。
  如果任务量超过了这个大小呢？比如下面所示，A、B、C、D 任务已经填满了这个表，而我们还有任务 F。这个时候其实我们直接将任务 F 加入到前面的执行周期就好了，为什么呢？执行周期的限制其实是对每列任务的限制，比如在这里，第一个周期的 A 执行过后，至少需要等待 2 个时间才能继续执行 A，那我们等到 3 个时间当然也是没有任何问题的。因此我们可以直接对每个执行周期任意延长。
  注意这里“延长”执行周期并不是对所有的执行周期都延长，而是只延长需要的，比如这里，前两个执行周期延长到了 4，而下面的执行周期依然是 3。这个时候我们可以发现，其实我们需要的时间数就是所有的任务数，这个时候我们已经不需要任何的“待命”时间了。

  通过上面的分析，我们知道所需时间要么是 (n+1)*(maxtimes-1)+diff，要么是任务数，是两者中更大的那个。那么我们就只需要计算出任务量最多的任务，以及它们的种数。我们使用一个哈希表来记录每个任务的任务量，之后再遍历哈希表找出任务量最多的任务种类即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> times;
        for(const char& ch : tasks){
            times[ch]++;
        }
        int maxtimes = 0, diff;
        for(const auto& it : times){
            if(it.second > maxtimes){
                maxtimes = it.second;
                diff = 1;
            }
            else if(it.second == maxtimes){
                diff++;
            }
        }
        // 这里注意 size() 的返回值是无符号数，需要进行强制类型转换
        return max((n+1)*(maxtimes-1)+diff, static_cast<int>(tasks.size()));
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是任务数。我们只需要遍历一次任务进行记录，再遍历一次哈希表获取结果，哈希表的大小不会超过 $n$。
  空间复杂度：$O(n)$，其中 $n$ 是任务数。也就是哈希表的开销。

  PS：上面的三个图来自 Leetcode 会员 popopop 发表的题解。由于我懒得画图，因此直接用同样的例子进行解释，然后就套用了 ta 的图，在这里表示感谢。