題目描述:給定一個字符陣列 tasks(每個字符代表一種 CPU 任務)和非負整數 n,CPU 執行相同任務之間必須至少間隔 n 個時間單位(可插入其他任務或閒置)。請求最短完成所有任務所需的時間單位數。
解題思路:這是一道貪心問題,關鍵洞察在於:出現頻率最高的任務決定了整體下限。
設出現最多次的任務頻率為 maxFreq,有 countOfMaxFreq 種任務都達到此頻率。
貪心公式推導:
想像將最高頻任務的執行分成 maxFreq - 1 個「框架區塊」,每個區塊寬度為 n + 1(1 個高頻任務 + n 個間隔槽),加上最後一輪所有達到 maxFreq 的任務:
最少時間 = (maxFreq - 1) * (n + 1) + countOfMaxFreq
然而,若任務種類夠多,完全填滿所有間隔槽後仍有剩餘任務,此時無需任何 idle,最少時間就是 tasks.size()。
因此答案為:max((maxFreq - 1) * (n + 1) + countOfMaxFreq, tasks.size())
本解使用最大堆模擬:雖然公式法更快,模擬法更具教育意義且可應對變形題。使用最大堆(按頻率排序),每輪取出最多 n+1 個不同任務執行,每輪耗時為實際執行任務數(填滿 n+1)或最後一輪的實際數量。
時間複雜度:O(n_tasks * log 26) = O(n_tasks) — 任務種類最多 26 種(大寫字母),堆的大小最大為 26,每次堆操作為 O(log 26) = O(1) 常數。外層迴圈執行次數等於總輪數,每輪最多處理 26 個任務,總計 O(n_tasks)。
空間複雜度:O(26) = O(1) — 頻率表和最大堆的大小上限均為 26(字母種類數),視為常數空間。
1. Count the frequency of each task type. 2. Push all frequencies into a max-heap. 3. While the heap is not empty: a. Set cycle = n + 1 (available slots in this round). b. Pop up to (n+1) tasks from the heap (most frequent first), decrement each count, save non-zero counts. c. Push non-zero counts back into the heap. d. Add to total time: if heap is now empty, add only the actual tasks done this cycle; otherwise add (n+1) to account for idle slots. 4. Return total time.
數學公式法 O(n):直接計算答案而不模擬,一行即可:return max((int)tasks.size(), (maxFreq - 1) * (n + 1) + countOfMaxFreq)。先統計頻率找出 maxFreq 和達到 maxFreq 的任務種數 countOfMaxFreq,時間 O(n),空間 O(1)(只需頻率陣列大小 26)。這是面試中最推薦的解法,前提是能正確推導公式。
排序貪心 O(n log n):每輪將頻率陣列排序,取前 n+1 個頻率最高的任務執行並遞減,重複至全部完成。邏輯清晰但排序開銷大於堆。由於任務種類最多 26 種,排序實際上是 O(26 log 26) = O(1) 常數,整體仍為 O(n)。