HardRating 2276
1606. Find Servers That Handled Most Number of Requests
arrayheap-priority-queuesimulationordered-set
解題說明
Find Servers That Handled Most Number of Requests
題目描述： 有 k 台伺服器（編號 0 到 k-1），n 個請求依次到達。第 i 個請求到達時間為 arrival[i]，處理時間為 load[i]。請求 i 優先分配給伺服器 i % k，如果該伺服器忙碌，則依序嘗試下一台，直到找到空閒伺服器或所有伺服器都忙碌。回傳處理最多請求的伺服器列表。
解題思路： 使用一個有序集合（TreeSet / std::set）維護空閒伺服器的編號，以及一個優先佇列（min heap）維護忙碌伺服器的 (完成時間, 伺服器編號)。對每個請求：先將已完成的伺服器從優先佇列釋放到空閒集合，然後從空閒集合中找到 >= i % k 的第一台伺服器（用 lower_bound），如果沒找到則繞回從集合開頭找。
C++ 解法
複雜度分析
時間複雜度：O(n log k) — 每個請求的有序集合和優先佇列操作均為 O(log k)
空間複雜度：O(k + n) — 有序集合和優先佇列
虛擬碼
1. Initialize available set = {0, 1, ..., k-1}, busy min-heap, count[k] = 0
2. For each request i:
a. Release finished servers from busy heap to available set
b. If no available server, drop request
c. Find first available server >= (i % k) using lower_bound
d. If none found, wrap around to beginning of available set
e. Assign request to found server, move server to busy heap
f. Increment count[server]
3. Return all servers with maximum count其他解法
方法二：暴力模擬 對每個請求，從 i % k 開始逐一檢查 k 台伺服器是否空閒。時間複雜度 O(n × k)，當 k 和 n 都很大時會超時。
方法三：線段樹 用線段樹維護每台伺服器的完成時間，支援區間最小值查詢來找到最早空閒的伺服器。時間複雜度 O(n log k)，但實現較為複雜。
延伸思考
- 如果請求可以排隊等待（而非直接丟棄），你會如何修改資料結構？
- 如果伺服器的處理能力不同（有些伺服器更快），如何納入考量？
- 這個問題和負載平衡器（Load Balancer）的設計有什麼關聯？