LeetCode 解題筆記：1606. Find Servers That Handled Most Number of Requests

作者：王一哲
日期：2026年11月9日


LeetCode 題目連結：1606. Find Servers That Handled Most Number of Requests

解題想法

困難題。題目給一個整數 $k ~(1 \leq k \leq 10^5)$，代表有 $k$ 個伺服器，編號為 $0$ 到 $k-1$。再給一個陣列 $arrival$，$arrival[i]$ 代表任務 $i$ 送給伺服器的時刻。另一個陣列 $load$，$load[i]$ 代表任務 $i$ 需要在伺服器上工作的時間。指派第 $i$ 個任務給伺服器的原則如下：

1. 如果伺服器 $j = i \pmod k$ 有空，將任務指派給伺服器 $j$。
2. 如果伺服器 $j$ 工作中，依序往下找伺服器 $j+1, j+2, \dots$，將任務指派給第一個有空的伺服器。
3. 如果所有伺服器都在工作中，放棄這個任務。

要找出所有的伺服器當中，哪些編號的伺服器被指派最多任務，回傳這些伺服器的編號。

我的寫法是用 3 個最小優先佇列儲存伺服器資料，$ftime$ 記錄每個伺服器最快可用的時刻，內容為 $(time, index)$；$back$ 記錄編號在這次被指派任務的伺服器 $j$ 後面的伺服器；$front$ 記錄編號在這次被指派任務的伺服器 $j$ 前面的伺服器。開一個長度為 $k$ 的陣列 $cnt$ 記錄每個伺服器被指派的任務數量。依序讀取任務送出的時刻 $t$ 及編號 $i$，計算 $j = i \pmod k$，如果 $j = 0$，$front, back$ 的內容要交換。接下來用 whlie 迴圈，從 $ftime$ 前方找可用的伺服器，檢查編號 $s$，如果 $s \geq j$ 放入 $front$，反之放入 $back$。再來決定真正被指派任務的伺服器編號 $p$，如果 $front$ 有資料，$p$ 等於 $front$ 最小的項目；如果 $front$ 是空的，再找 $back$ 之中最小的項目；如果兩者都是空的，放棄這個任務。如果有找到 $p$，將 $cnt[p]$ 加 1，$(t + load[i], p)$ 加入 $ftime$。

Python 程式碼

Runtime: 250 ms, beats 92.23%. Memory: 45.78 MB, beats 50.68%.

class Solution:
    def busiestServers(self, k: int, arrival: list[int], load: list[int]) -> list[int]:
        cnt = [0] * k  # 每個伺服器的工作數量
        
        # priority queue，每個伺服器最快可用的時刻，內容為 (time, index)，先放入不可能的值 */
        ftime = [(1000000001, -1)]
        
        # 目前可用的伺服器，往前找（編號大）為 front，往後找（編號小）為 back */
        back, front = list(range(k)), []
        
        # 主要的解題過程
        n = len(arrival)
        for i in range(n):  # 依序讀取工作索引值 i、派送時刻 t
            t = arrival[i]
            j = i % k  # 理論上要用的伺服器編號 j
            if j == 0:  # j 等於 0，交換 front, back
                front, back = back, front

            while ftime and ftime[0][0] <= t:  # ftime 前方找可用的伺服器，還要檢查編號
                s = heapq.heappop(ftime)[1]  # 取出可用的的伺服器編號 s
                if s >= j:  # 如果 s 大於等於 j，加入 front
                    heapq.heappush(front, s)
                else:  # 如果 s 小於 j，加入 back
                    heapq.heappush(back, s)
            
            p = -1  # 真正要用的伺服器編號
            if front:  # 如果 front 有內容，取出最小值存到 p，移除最小值
                p = heapq.heappop(front)
            elif back:  # 如果 front 沒有內容，back 有內容，取出最小值存到 p，移除最小值
                p = heapq.heappop(back)
            else:  # 如果沒有可用的伺服器，放棄這個工作，執行下一次
                continue
            
            cnt[p] += 1  # 編號 p 的伺服器工作數加 1
            
            heapq.heappush(ftime, (t + load[i], p))  # 將伺服器 p 及下一個可用時刻加入 ftime
        
        # 準備要回傳的答案
        imax = max(cnt)  # 所有伺服器中最多的工作數量
        ans = [i for i in range(k) if cnt[i] == imax]   # 將等於 imax 的伺服器編號加入 ans
        return ans

C++ 程式碼

Runtime: 63 ms, beats 99.06%. Memory: 97.27 MB, beats 97.48%.

class Solution {
public:
    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
        vector<int> cnt (k, 0);  // 每個伺服器的工作數量
        /* priority queue，每個伺服器最快可用的時刻，內容為 (time, index)，先放入不可能的值 */
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> ftime;
        ftime.push({1000000001, -1});
        /* 目前可用的伺服器，往前找（編號大）為 front，往後找（編號小）為 back */
        priority_queue<int, vector<int>, greater<int>> back, front;
        for(int i = 0; i < k; i++) back.push(i);
        
        /* 主要的解題過程 */
        int n = arrival.size();
        for(int i = 0; i < n; i++) {// 依序讀取工作索引值 i、派送時刻 t
            int t = arrival[i];
            int j = i % k;  // 理論上要用的伺服器編號 j
            if (j == 0) swap(front, back);  // j 等於 0，交換 front, back
            while(ftime.top().first <= t) {  // ftime 前方找可用的伺服器，還要檢查編號
                int s = ftime.top().second;  // 取出可用的的伺服器編號 s
                ftime.pop();  // 移除最上面的值
                if (s >= j) front.push(s);  // 如果 s 大於等於 j，加入 front
                else back.push(s);  // 如果 s 小於 j，加入 back
            }

            int p;  // 真正要用的伺服器編號
            if (!front.empty()) {  // 如果 front 有內容，取出最小值存到 p，移除最小值
                p = front.top();
                front.pop();
            } else if (!back.empty()) {  // 如果 front 沒有內容，back 有內容，取出最小值存到 p，移除最小值
                p = back.top();
                back.pop();
            } else {  // 如果沒有可用的伺服器，放棄這個工作，執行下一次 for 迴圈
                continue;
            }

            cnt[p]++;  // 編號 p 的伺服器工作數加 1
            ftime.push({t + load[i], p});  // 將伺服器 p 及下一個可用時刻加入 ftime
        }
        
        /* 準備要回傳的答案 */
        int imax = *max_element(cnt.begin(), cnt.end());  // 所有伺服器中最多的工作數量
        vector<int> ans;  // 儲存答案的 vector
        for(int i = 0; i < k; i++) {  // 依序讀取每個伺服器的工作數量
            if (cnt[i] == imax) ans.push_back(i);  // 將等於 imax 的伺服器編號加入 ans
        }
        return ans;  // 回傳答案
    }
};