621. Task Scheduler

Medium

Description

給定一個字元陣列 tasks（代表 CPU 要執行的任務）和冷卻間隔 n。相同任務之間必須間隔至少 n 個時間單位。CPU 可以執行不同任務或閒置。求完成所有任務需要的最少時間單位。

Example:

Input: tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2 Output: 8

Intuition#

核心思路：頻率最高的任務決定了最少時間的下界，用 Max Heap + Queue 貪心排程。

頻率最高的任務之間必須間隔 n，形成 (maxFreq - 1) 個間隔
每個間隔大小為 n + 1（包含任務本身），用其他任務填滿間隔
貪心策略：優先排頻率最高的任務，用 Max Heap 確保每次選最高頻的

Approaches#

1: Math / Greedy 公式法#

概念: 最少時間 = max(任務總數, (maxFreq - 1) * (n + 1) + maxCount)，其中 maxCount 是頻率等於 maxFreq 的任務數
時間複雜度: O(n) - n 為任務數
空間複雜度: 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 模擬#

概念: 用 Max Heap 存各任務剩餘次數，每個時間單位取出頻率最高的執行。已執行的任務加入等待佇列，冷卻結束後再放回 Heap
時間複雜度: O(m * n) - m 為任務總數（最壞情況每個任務都需等待）
空間複雜度: 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 + 冷卻佇列的組合
關鍵技巧: 公式法更快但需要推導；Heap 模擬法更直觀且容易推廣到變體題；理解「最高頻任務決定下界」是關鍵