題目描述:
給定 n 個任務,每個任務有 [enqueueTime, processingTime]。CPU 為單執行緒:空閒時從已到達的任務中選處理時間最短的執行(相同時選索引小的)。若無任務可執行,CPU 跳到下一個任務的入隊時間。回傳任務執行順序。
解題思路:
(processingTime, index) 排序。enqueueTime <= currentTime 的任務加入堆。currentTime += processingTime。時間複雜度: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)替代堆,支持同樣的最小值查詢。複雜度相同但常數因子可能較大。