LC 621. 任务调度器

题目描述

这是 LeetCode 上的 621. 任务调度器 ，难度为 中等。

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，其中每个字母表示一种不同种类的任务。

任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。

在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

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

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

示例 1：

输入：tasks = ["A","A","A","B","B","B"], n = 2

输出：8

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

示例 2：

输入：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：

输入：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]$

---

构造

先考虑最为简单的情况：假设只有一类任务，除了最后一个任务以外，其余任务在安排后均需要增加 $n$ 个单位的冻结时间。

将任务数记为 $m$ 个，其中前 $m - 1$ 个任务均要消耗 $n + 1$ 的单位时间，最后一个任务仅消耗 $1$ 个单位时间，即所需要的时间为 $(n + 1) \times (m - 1) + 1$。

当存在多个任务时，由于每一类任务都需要被完成，因此本质上我们最需要考虑的是将数量最大的任务安排掉，其他任务则是间插其中。

假设数量最大的任务数为 max，共有 tot 个任务数为 max 的任务种类。

实际上，当任务总数不超过 $(n + 1) \times (\max - 1) + tot$ 时，我们总能将其他任务插到空闲时间中去，不会引入额外的冻结时间（下左图）；而当任务数超过该值时，我们可以在将其横向添加每个 $n + 1$ 块的后面，同时不会引入额外的冻结时间（下右图）：

综上，我们所需要的最小时间为上述两种情况中的较大值即可：

$$\max(task.length, (n + 1) \times (max - 1) + tot)$$

Java 代码：

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] cnts = new int[26];
        for (char c : tasks) cnts[c - 'A']++;
        int max = 0, tot = 0;
        for (int i = 0; i < 26; i++) max = Math.max(max, cnts[i]);
        for (int i = 0; i < 26; i++) tot += max == cnts[i] ? 1 : 0;
        return Math.max(tasks.length, (n + 1) * (max - 1) + tot);
    }
}

C++ 代码：

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> cnts(26, 0);
        for (char c : tasks) cnts[c - 'A']++;
        int maxv = *max_element(cnts.begin(), cnts.end());
        int tot = count(cnts.begin(), cnts.end(), maxv);
        return max(static_cast<int>(tasks.size()), (n + 1) * (maxv - 1) + tot);
    }
};

Python 代码：

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        cnts = [0] * 26
        for c in tasks:
            cnts[ord(c) - ord('A')] += 1
        maxv, tot = 0, 0
        for i in range(26):
            maxv = max(maxv, cnts[i])
        for i in range(26):
            tot += 1 if maxv == cnts[i] else 0
        return max(len(tasks), (n + 1) * (maxv - 1) + tot)

TypeScript 代码：

function leastInterval(tasks: string[], n: number): number {
    const cnts = new Array<number>(26).fill(0)
    for (const c of tasks) cnts[c.charCodeAt(0) - 'A'.charCodeAt(0)]++
    let max = 0, tot = 0
    for (let i = 0; i < 26; i++) max = Math.max(max, cnts[i])
    for (let i = 0; i < 26; i++) tot += max == cnts[i] ? 1 : 0
    return Math.max(tasks.length, (n + 1) * (max - 1) + tot)
}

• 时间复杂度：$O(n + C)$
• 空间复杂度：$O(C)$，其中 $C = 26$ 为任务字符集大小

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.621 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。