Description
給定
tasks[i] = [enqueueTime, processingTime]，表示第 i 個任務在 enqueueTime 可用，需要 processingTime 時間處理。CPU 單執行緒，同時可用的任務中選 processingTime 最小的先執行（相同則選 index 小的）。回傳 CPU 處理任務的順序。
Example:
Input: tasks = [[1,2],[2,4],[3,2],[4,1]] Output: [0,2,3,1]
Intuition#
核心思路：模擬 CPU 排程，用 Min Heap 依 processingTime 排序可用任務，依時間順序處理。
- 這是一個事件驅動的模擬題
- 先依 enqueueTime 排序，方便依時間加入任務
- 用 Min Heap 維護目前可用的任務，按 (processingTime, index) 排序
- 當 heap 為空但還有任務時，快轉到下一個任務的 enqueueTime
Approaches#
⭐1: Sorting + Min Heap 模擬#
- 概念: 依時間排序任務，用 Min Heap 管理可用任務佇列，模擬 CPU 執行流程
- 時間複雜度:
O(n log n)- 排序 + heap 操作 - 空間複雜度:
O(n)
class Solution {
fun getOrder(tasks: Array<IntArray>): IntArray {
val n = tasks.size
val indexed = Array(n) { intArrayOf(tasks[it][0], tasks[it][1], it) }
indexed.sortBy { it[0] }
// Min Heap: (processingTime, originalIndex)
val heap = PriorityQueue<IntArray>(compareBy({ it[1] }, { it[2] }))
val result = IntArray(n)
var time = 0L
var i = 0
var ri = 0
while (ri < n) {
// 若 heap 為空且還有任務，快轉時間
if (heap.isEmpty() && i < n && time < indexed[i][0]) {
time = indexed[i][0].toLong()
}
// 加入所有在 time 之前（含）可用的任務
while (i < n && indexed[i][0] <= time) {
heap.offer(indexed[i])
i++
}
// 執行最優先的任務
val task = heap.poll()
result[ri++] = task[2]
time += task[1]
}
return result
}
}🔑 Takeaways#
- Pattern: 事件驅動模擬 + Priority Queue 排程
- 關鍵技巧: 需要保留原始 index 用於輸出和 tie-breaking；當 heap 為空時要快轉時間避免無限迴圈；注意使用 Long 避免時間溢位