1882. Process Tasks Using Servers

Medium
Description

給定 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#

核心思路：用兩個 Heap 分別管理空閒伺服器和忙碌伺服器，模擬任務分配過程。

  • 空閒 Heap (free)：按 (weight, index) 排序
  • 忙碌 Heap (busy)：按 (完成時間, weight, index) 排序
  • 每個時間點先把完成的伺服器移回 free，再分配任務
  • 若沒有空閒伺服器，快轉到最近的伺服器完成時間

Approaches#

⭐1: 雙 Heap 模擬#

  • 概念: free heap 管理可用伺服器，busy heap 管理正在工作的伺服器，按時間步進模擬
  • 時間複雜度: O((n + m) log m) - n 為任務數，m 為伺服器數
  • 空間複雜度: 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 模式：一個管理可用資源，一個管理正在使用的資源
  • 關鍵技巧: 當無可用資源時，快轉時間到最近的釋放時間；busy heap 的排序條件要包含 weight 和 index 以正確 tie-break