給你一個用字符數組?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⁴
• tasks[i] 是大寫英文字母
• n 的取值范圍為 [0, 100]

構造

我們首先考慮所有任務種類中執行次數最多的那一種，記它為 $\text{A}$，的執行次數為 $\text{maxExec}$。

我們使用一個寬為 $n+1$ 的矩陣可視化地展現執行 $\text{A}$ 的時間點。其中任務以行優先的順序執行，沒有任務的格子對應 CPU 的待命狀態。由于冷卻時間為 $n$，因此我們將所有的 $\text{A}$ 排布在矩陣的第一列，可以保證滿足題目要求，并且容易看出這是可以使得總時間最小的排布方法，對應的總時間為：

$$(\text{maxExec}?1)(n+1)+1$$

同理，如果還有其它也需要執行 $\text{maxExec}$ 次的任務，我們也需要將它們依次排布成列。例如，當還有任務 $\text{B}$ 和 $\text{C}$ 時，我們需要將它們排布在矩陣的第二、三列。

如果需要執行 $\text{maxExec}$ 次的任務的數量為 $\text{maxCount}$，那么類似地可以得到對應的總時間為：

$$(\text{maxExec}?1)(n+1)+\text{maxCount}$$

讀者可能會對這個總時間產生疑問：如果 $\text{maxCount}>n+1$，那么多出的任務會無法排布進矩陣的某一列中，上面計算總時間的方法就不對了。我們把這個疑問放在這里，先「假設」一定有 $\text{maxCount}\le n+1$。

處理完執行次數為 $\text{maxExec}$ 次的任務，剩余任務的執行次數一定都小于 $\text{maxExec}$，那么我們應當如何將它們放入矩陣中呢？一種構造的方法是，我們從倒數第二列開始，按照反向列優先的順序（即先放入靠左側的列，同一列中先放入下方的行），依次放入每一種任務，并且同一種任務需要連續地填入。例如還有任務 $\text{D}$，$\text{E}$ 和 $\text{F}$ 時，我們會按照下圖的方式依次放入這些任務。

對于任意一種任務而言，一定不會被放入同一行兩次（否則說明該任務的執行次數大于等于 $\text{maxExec}$），并且由于我們是按照列優先的順序放入這些任務，因此任意兩個相鄰的任務之間要么間隔 $n$（例如上圖中位于同一列的相同任務），要么間隔 $n+1$（例如上圖中第一列和第二列的 $\text{F}$），都是滿足題目要求的。因此如果我們按照這樣的方法填入所有的任務，那么就可以保證總時間不變，仍然為：

$$(\text{maxExec}?1)(n+1)+\text{maxCount}$$

當然，這些都建立在我們的「假設」之上，即我們不會填「超出」$n+1$ 列。但讀者可以想一想，如果我們真的填「超出」了 $n+1$ 列，會發生什么呢？

上圖給出了一個例子，此時 $n+1=5$ 但我們填了 $7$ 列。標記為 $\text{X}$ 的格子表示 CPU 的待命狀態。看上去我們需要 $(5?1)\times 7+4=32$ 的時間來執行所有任務，但實際上如果我們填「超出」了 $n+1$ 列，那么所有的 CPU 待命狀態都是可以省去的。這是因為 CPU 待命狀態本身只是為了規定任意兩個相鄰任務的執行間隔至少為 $n$，但如果列數超過了 $n+1$，那么就算沒有這些待命狀態，任意兩個相鄰任務的執行間隔肯定也會至少為 $n$。此時，總執行時間就是任務的總數 $|\text{task}|$。

同時我們可以發現：

• 如果我們沒有填「超出」了 $n+1$ 列，那么圖中存在 $0$ 個或多個位置沒有放入任務，由于位置數量為 $(\text{maxExec}?1)(n+1)+\text{maxCount}$，因此有：

  $$|\text{task}|<(\text{maxExec}?1)(n+1)+\text{maxCount}$$

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

  $$|\text{task}|>(\text{maxExec}?1)(n+1)+\text{maxCount}$$

因此，在任意的情況下，需要的最少時間就是 $(\text{maxExec}?1)(n+1)+\text{maxCount}$ 和 $|\text{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))

總結

以上是生活随笔為你收集整理的621. Task Scheduler 任务调度器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。