解題說明
Process Tasks Using Servers
題目描述:
給定 servers 陣列(每台伺服器的權重)和 tasks 陣列(每個任務的處理時間)。任務按時間 0, 1, 2, ... 依序到達。空閒的伺服器中選權重最小的(相同則選索引小的)來處理任務。若無空閒伺服器,等到最早有伺服器空閒時再分配。回傳每個任務分配到的伺服器索引。
解題思路: 使用兩個最小堆:
free:空閒伺服器堆,按(weight, index)排序。busy:忙碌伺服器堆,按(endTime, weight, index)排序。
模擬流程:
- 對於時間 t 到達的任務 t:
- 先將所有
endTime <= t的忙碌伺服器放回 free 堆。 - 若 free 堆非空,取出最優伺服器,放入 busy 堆(endTime = t + tasks[t])。
- 若 free 堆為空,取 busy 堆頂的伺服器(最早結束),等到它結束後分配。
- 先將所有
C++ 解法
複雜度分析
時間複雜度:O((m + n) log m) — 初始化 free 堆 O(m log m),每個任務最多引發 O(log m) 的堆操作。
空間複雜度:O(m + n) — 兩個堆共存 m 個伺服器,結果陣列 O(n)。
虛擬碼
1. Initialize free heap with all servers as (weight, index)
2. Initialize empty busy heap for (endTime, weight, index)
3. For each task t arriving at time t:
a. Move all servers with endTime <= t from busy to free
b. If free is not empty:
- Pop best server, assign to task t
- Push to busy with endTime = t + tasks[t]
c. Else:
- Pop the server finishing earliest from busy
- Release all servers finishing at same time to free
- Assign this server, push to busy with endTime = endTime + tasks[t]
4. Return assignment result其他解法
TreeMap 代替堆 O((m+n) log m):用有序映射(如 C++ std::set)管理空閒伺服器,支持相同的最小值查詢。功能等價但程式碼可能更複雜。
暴力模擬 O(n × m):對每個任務,線性掃描所有伺服器找空閒且權重最小的。簡單但 n 和 m 大時超時。
延伸思考
- 如果任務有優先級(高優先級任務可以搶佔低優先級任務),如何修改模擬邏輯?
- 如果伺服器有最大負載限制(可同時處理 k 個任務),如何調整資料結構?
- 如果要最小化所有任務的總等待時間,是否有比貪心更優的策略?