解題說明
Single-Threaded CPU
題目描述：
給定 n 個任務，每個任務有 [enqueueTime, processingTime]。CPU 為單執行緒：空閒時從已到達的任務中選處理時間最短的執行（相同時選索引小的）。若無任務可執行，CPU 跳到下一個任務的入隊時間。回傳任務執行順序。
解題思路：
- 將任務附上原始索引後，按入隊時間排序。
- 用最小堆（min-heap）管理已到達但未處理的任務，按
(processingTime, index)排序。 - 模擬時間線：
- 將所有
enqueueTime <= currentTime的任務加入堆。 - 從堆中取出最優任務執行，
currentTime += processingTime。 - 若堆為空且還有任務，跳到下一個任務的入隊時間。
- 將所有
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 排序 O(n log n)，每個任務最多入堆出堆各一次，每次 O(log n)。
空間複雜度：O(n) — 排序陣列和堆各需 O(n) 空間。
虛擬碼
1. Attach original index to each task, sort by enqueueTime 2. Create min-heap ordered by (processingTime, originalIndex) 3. Initialize time = 0, pointer idx = 0, result = [] 4. While idx < n or heap is not empty: a. If heap is empty and next task hasn't arrived: time = sorted[idx].enqueueTime b. Enqueue all tasks with enqueueTime <= time into heap c. Pop task with smallest (processingTime, index) from heap d. Append its original index to result e. time += processingTime 5. Return result
其他解法
暴力模擬 O(n²)：每次從所有已到達的未處理任務中線性掃描找最短處理時間的任務。簡單但 n 大時超時。
TreeMap/有序集合 O(n log n)：用平衡二元搜尋樹（如 C++ 的 std::set）替代堆，支持同樣的最小值查詢。複雜度相同但常數因子可能較大。
延伸思考
- 如果 CPU 是多核（可同時處理 k 個任務），如何修改模擬邏輯？
- 如果任務有優先級（不僅看處理時間），如何調整堆的比較規則？
- 如果需要計算每個任務的等待時間而非執行順序，該如何修改？