給定
servers陣列（每個伺服器的權重）和tasks陣列（每個任務的處理時間）。第 j 個任務在時間 j 到達。分配規則：優先選權重最小的空閒伺服器（權重相同選 index 小的）。若無空閒則等待。回傳每個任務被分配到的伺服器 index。
Example:
Input: servers = [3,3,2], tasks = [1,2,3,2,1,2] Output: [2,2,0,2,1,2]
Intuition
TIP
核心思路：用兩個 Heap 分別管理空閒伺服器和忙碌伺服器，模擬任務分配過程。
- 空閒 Heap (free)：按 (weight, index) 排序
- 忙碌 Heap (busy)：按 (完成時間, weight, index) 排序
- 每個時間點先把完成的伺服器移回 free，再分配任務
- 若沒有空閒伺服器，快轉到最近的伺服器完成時間
Approaches
1. Brute-Force Simulation: Scan All Servers per Task — O(n·m) / O(m)
- Idea: 用
freeAt[]記每台伺服器下次可用時間；每個任務在max(t, 最早可用)時，掃 m 台選 (weight, index) 最小的空閒者 - Time:
O(n·m)- 每個任務掃 m 台 - Space:
O(m)
class Solution {
fun assignTasks(servers: IntArray, tasks: IntArray): IntArray {
val m = servers.size; val n = tasks.size
val freeAt = LongArray(m) // 每台伺服器下次可用時間
val res = IntArray(n)
for (t in 0 until n) {
var now = t.toLong()
if ((0 until m).none { freeAt[it] <= now }) { // 無人空閒 → 快轉
now = (0 until m).minOf { freeAt[it] }
}
var best = -1
for (i in 0 until m) {
if (freeAt[i] <= now &&
(best == -1 || servers[i] < servers[best] ||
(servers[i] == servers[best] && i < best))) best = i
}
res[t] = best
freeAt[best] = now + tasks[t]
}
return res
}
}⭐ 2. Two Heaps Simulation — O((n + m) log m) / O(m + n)
- Idea: free heap 管理可用伺服器，busy heap 管理正在工作的伺服器，按時間步進模擬
- Time:
O((n + m) log m)- n 為任務數，m 為伺服器數 - Space:
O(m + n)
class Solution {
fun assignTasks(servers: IntArray, tasks: IntArray): IntArray {
val m = servers.size
val n = tasks.size
// free: (weight, index)
val free = PriorityQueue<IntArray>(compareBy({ it[0] }, { it[1] }))
for (i in 0 until m) {
free.offer(intArrayOf(servers[i], i))
}
// busy: (finishTime, weight, index)
val busy = PriorityQueue<IntArray>(compareBy({ it[0] }, { it[1] }, { it[2] }))
val result = IntArray(n)
for (t in 0 until n) {
val time = t.toLong()
// 釋放已完成的伺服器
while (busy.isNotEmpty() && busy.peek()[0] <= time) {
val server = busy.poll()
free.offer(intArrayOf(server[1], server[2]))
}
if (free.isEmpty()) {
// 快轉到最近完成的伺服器
val earliest = busy.peek()[0].toLong()
while (busy.isNotEmpty() && busy.peek()[0].toLong() == earliest) {
val server = busy.poll()
free.offer(intArrayOf(server[1], server[2]))
}
val server = free.poll()
result[t] = server[1]
busy.offer(intArrayOf((earliest + tasks[t]).toInt(), servers[server[1]], server[1]))
} else {
val server = free.poll()
result[t] = server[1]
busy.offer(intArrayOf(t + tasks[t], servers[server[1]], server[1]))
}
}
return result
}
}🔑 Takeaways
- Pattern: 雙 Heap 模式：一個管理可用資源，一個管理正在使用的資源
- Key trick: 當無可用資源時，快轉時間到最近的釋放時間；busy heap 的排序條件要包含 weight 和 index 以正確 tie-break