給定一個字元陣列
tasks（代表 CPU 要執行的任務）和冷卻間隔n。相同任務之間必須間隔至少n個時間單位。CPU 可以執行不同任務或閒置。求完成所有任務需要的最少時間單位。
Example:
Input: tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2 Output: 8
Intuition
TIP
核心思路：頻率最高的任務決定了最少時間的下界，用 Max Heap + Queue 貪心排程。
- 頻率最高的任務之間必須間隔 n，形成 (maxFreq - 1) 個間隔
- 每個間隔大小為 n + 1（包含任務本身），用其他任務填滿間隔
- 貪心策略：優先排頻率最高的任務，用 Max Heap 確保每次選最高頻的
Approaches
1. Math / Greedy Formula — O(n) / O(1)
- Idea: 最少時間 = max(任務總數, (maxFreq - 1) * (n + 1) + maxCount)，其中 maxCount 是頻率等於 maxFreq 的任務數
- Time:
O(n)- n 為任務數 - Space:
O(1)- 最多 26 個字母
class Solution {
fun leastInterval(tasks: CharArray, n: Int): Int {
val freq = IntArray(26)
for (task in tasks) freq[task - 'A']++
val maxFreq = freq.max()
val maxCount = freq.count { it == maxFreq }
return maxOf(tasks.size, (maxFreq - 1) * (n + 1) + maxCount)
}
}⭐ 2. Max Heap + Queue Simulation — O(m * n) / O(1)
- Idea: 用 Max Heap 存各任務剩餘次數，每個時間單位取出頻率最高的執行。已執行的任務加入等待佇列，冷卻結束後再放回 Heap
- Time:
O(m * n)- m 為任務總數（最壞情況每個任務都需等待） - Space:
O(1)- 最多 26 個任務種類
class Solution {
fun leastInterval(tasks: CharArray, n: Int): Int {
val freq = IntArray(26)
for (task in tasks) freq[task - 'A']++
val maxHeap = PriorityQueue<Int>(compareByDescending { it })
for (f in freq) {
if (f > 0) maxHeap.offer(f)
}
var time = 0
val queue: ArrayDeque<Pair<Int, Int>> = ArrayDeque() // (remaining count, available time)
while (maxHeap.isNotEmpty() || queue.isNotEmpty()) {
time++
if (maxHeap.isNotEmpty()) {
val cnt = maxHeap.poll() - 1
if (cnt > 0) {
queue.addLast(cnt to time + n)
}
}
if (queue.isNotEmpty() && queue.first().second == time) {
maxHeap.offer(queue.removeFirst().first)
}
}
return time
}
}🔑 Takeaways
- Pattern: 排程問題常見 Heap + 冷卻佇列的組合
- Key trick: 公式法更快但需要推導；Heap 模擬法更直觀且容易推廣到變體題；理解「最高頻任務決定下界」是關鍵