621. Task Scheduler 任务调度器

给你一个用字符数组 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 <= 104
• tasks[i] 是大写英文字母
• n 的取值范围为 [0, 100]

构造

我们首先考虑所有任务种类中执行次数最多的那一种，记它为 A\texttt{A}A，的执行次数为 maxExec\textit{maxExec}maxExec。

我们使用一个宽为 n+1n+1n+1 的矩阵可视化地展现执行 A\texttt{A}A 的时间点。其中任务以行优先的顺序执行，没有任务的格子对应 CPU 的待命状态。由于冷却时间为 nnn，因此我们将所有的 A\texttt{A}A 排布在矩阵的第一列，可以保证满足题目要求，并且容易看出这是可以使得总时间最小的排布方法，对应的总时间为：

(maxExec−1)(n+1)+1(\textit{maxExec} - 1)(n + 1) + 1 (maxExec−1)(n+1)+1

同理，如果还有其它也需要执行 maxExec\textit{maxExec}maxExec 次的任务，我们也需要将它们依次排布成列。例如，当还有任务 B\texttt{B}B 和 C\texttt{C}C 时，我们需要将它们排布在矩阵的第二、三列。

如果需要执行 maxExec\textit{maxExec}maxExec 次的任务的数量为 maxCount\textit{maxCount}maxCount，那么类似地可以得到对应的总时间为：

(maxExec−1)(n+1)+maxCount(\textit{maxExec} - 1)(n + 1) + \textit{maxCount} (maxExec−1)(n+1)+maxCount

读者可能会对这个总时间产生疑问：如果 maxCount>n+1\textit{maxCount} > n+1maxCount>n+1，那么多出的任务会无法排布进矩阵的某一列中，上面计算总时间的方法就不对了。我们把这个疑问放在这里，先「假设」一定有 maxCount≤n+1\textit{maxCount} \leq n+1maxCount≤n+1。

处理完执行次数为 maxExec\textit{maxExec}maxExec 次的任务，剩余任务的执行次数一定都小于 maxExec\textit{maxExec}maxExec，那么我们应当如何将它们放入矩阵中呢？一种构造的方法是，我们从倒数第二列开始，按照反向列优先的顺序（即先放入靠左侧的列，同一列中先放入下方的行），依次放入每一种任务，并且同一种任务需要连续地填入。例如还有任务 D\texttt{D}D，E\texttt{E}E 和 F\texttt{F}F 时，我们会按照下图的方式依次放入这些任务。

对于任意一种任务而言，一定不会被放入同一行两次（否则说明该任务的执行次数大于等于 maxExec\textit{maxExec}maxExec），并且由于我们是按照列优先的顺序放入这些任务，因此任意两个相邻的任务之间要么间隔 nnn（例如上图中位于同一列的相同任务），要么间隔 n+1n+1n+1（例如上图中第一列和第二列的 F\texttt{F}F），都是满足题目要求的。因此如果我们按照这样的方法填入所有的任务，那么就可以保证总时间不变，仍然为：

(maxExec−1)(n+1)+maxCount(\textit{maxExec} - 1)(n + 1) + \textit{maxCount} (maxExec−1)(n+1)+maxCount

当然，这些都建立在我们的「假设」之上，即我们不会填「超出」n+1n+1n+1 列。但读者可以想一想，如果我们真的填「超出」了 n+1n+1n+1 列，会发生什么呢？

上图给出了一个例子，此时 n+1=5n+1=5n+1=5 但我们填了 777 列。标记为 X\texttt{X}X 的格子表示 CPU 的待命状态。看上去我们需要 (5−1)×7+4=32(5-1) \times 7 + 4 = 32(5−1)×7+4=32 的时间来执行所有任务，但实际上如果我们填「超出」了 n+1n+1n+1 列，那么所有的 CPU 待命状态都是可以省去的。这是因为 CPU 待命状态本身只是为了规定任意两个相邻任务的执行间隔至少为 nnn，但如果列数超过了 n+1n+1n+1，那么就算没有这些待命状态，任意两个相邻任务的执行间隔肯定也会至少为 nnn。此时，总执行时间就是任务的总数 ∣task∣|\textit{task}|∣task∣。

同时我们可以发现：

• 如果我们没有填「超出」了 n+1n+1n+1 列，那么图中存在 000 个或多个位置没有放入任务，由于位置数量为 (maxExec−1)(n+1)+maxCount(\textit{maxExec} - 1)(n + 1) + \textit{maxCount}(maxExec−1)(n+1)+maxCount，因此有：

  ∣task∣<(maxExec−1)(n+1)+maxCount|\textit{task}| < (\textit{maxExec} - 1)(n + 1) + \textit{maxCount} ∣task∣<(maxExec−1)(n+1)+maxCount

• 如果我们填「超出」了 n+1n+1n+1 列，那么同理有：

  ∣task∣>(maxExec−1)(n+1)+maxCount|\textit{task}| > (\textit{maxExec} - 1)(n + 1) + \textit{maxCount} ∣task∣>(maxExec−1)(n+1)+maxCount

因此，在任意的情况下，需要的最少时间就是 (maxExec−1)(n+1)+maxCount(\textit{maxExec} - 1)(n + 1) + \textit{maxCount}(maxExec−1)(n+1)+maxCount 和 ∣task∣|\textit{task}|∣task∣ 中的较大值。

Python

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freq = collections.Counter(tasks)
        maxExec = max(freq.values())
        maxCount = sum(1 for v in freq.values() if v == maxExec)
        return max((maxExec - 1) * (n + 1) + maxCount, len(tasks))