給定
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
TIP
核心思路：模擬 CPU 排程，用 Min Heap 依 processingTime 排序可用任務，依時間順序處理。
- 這是一個事件驅動的模擬題
- 先依 enqueueTime 排序，方便依時間加入任務
- 用 Min Heap 維護目前可用的任務，按 (processingTime, index) 排序
- 當 heap 為空但還有任務時，快轉到下一個任務的 enqueueTime
Approaches
1. Brute-Force Simulation: Pick Shortest Task per Step — O(n²) / O(n)
- Idea: 每輪線性掃所有未做、已可用的任務，挑處理時間最短（同則索引小）者；沒有可用就快轉時間
- Time:
O(n²)- n 輪、每輪掃描 O(n) - Space:
O(n)
class Solution {
fun getOrder(tasks: Array<IntArray>): IntArray {
val n = tasks.size
val done = BooleanArray(n)
val result = IntArray(n)
var time = 0L
fun pick(): Int {
var best = -1
for (i in 0 until n) {
if (done[i] || tasks[i][0] > time) continue
if (best == -1 || tasks[i][1] < tasks[best][1] ||
(tasks[i][1] == tasks[best][1] && i < best)) best = i
}
return best
}
for (r in 0 until n) {
var best = pick()
if (best == -1) { // 沒有可用任務 → 快轉到最早 enqueue 時間
var next = Long.MAX_VALUE
for (i in 0 until n) if (!done[i]) next = minOf(next, tasks[i][0].toLong())
time = next
best = pick()
}
done[best] = true
result[r] = best
time += tasks[best][1]
}
return result
}
}⭐ 2. Sorting + Min-Heap Simulation — O(n log n) / O(n)
- Idea: 依時間排序任務，用 Min Heap 管理可用任務佇列，模擬 CPU 執行流程
- Time:
O(n log n)- 排序 + heap 操作 - Space:
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 排程
- Key trick: 需要保留原始 index 用於輸出和 tie-breaking；當 heap 為空時要快轉時間避免無限迴圈；注意使用 Long 避免時間溢位