LeetCode 解題筆記：2747. Count Zero Request Servers

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


LeetCode 題目連結：2747. Count Zero Request Servers

解題想法

中等難度題。題目給一個整數 $n$，代表有 $n$ 個伺服器，編號為 $1$ 到 $n$。再給一個二維陣列 $logs$，每個元素裡有兩個數字 $idx, t$，代表編號為 $idx$ 的伺服器在時間 $t$ 收到請求開始工作。接下來給一個整數 $x$，代表要查詢的時間寬度。最後給一個陣列 $queries$，代表要查詢的時刻，計算在時間 $queries[i] - x \leq t \leq queries[i]$ 之間有幾個伺服器閒置。最後回傳每次查詢的答案。

將詢問的時刻 $t$ 及原始的索引值 $idx$ 組成 tuple 或 pair，存入陣列 sorted_queries，再依照 $t$ 將 sorted_queries 排序。再將 $logs$ 依照時刻排序。開一個長度為 $n+1$ 的陣列 $cnt$，記錄每一個伺服器目前的請求數量。開一個長度與 $queries$ 等長的陣列 $ans$，記錄每一次查詢的答案。

接下來用滑動視窗解題。假設視窗左端點 $left$ 從 0 開始，右端點 $right$ 從 0 開始，正在工作的伺服器數量 $active$ 預設為 0。依序讀取查詢的時刻 $t$ 及原始索引值 $query$，先用一個 while 迴圈新增時刻小於、等於 $t$ 的請求，如果某個伺服器的請求數量原為 0 並收到請求，則 $active + 1$；再用一個 while 迴圈移除時刻小於 $t - x$ 的請求，如果某個伺服器的請求數量原為 1，則 $active - 1$；最後更新 $ans[query] = n - active$。

Python 程式碼

Runtime: 133 ms, beats 90.00%. Memory: 68.06 MB, beats 92.73%.

class Solution:
    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
        # 將詢問及原始的索引值組成 tuple，再依照時刻排序
        sorted_queries = sorted((t, idx) for idx, t in enumerate(queries))
        
        # logs 依照時刻排序
        m = len(logs)
        logs.sort(key = lambda x : x[1])
        
        # 用 cnt 記錄伺服器收到的請求數量，如果某個伺服器的請求數量由 0 變成 1，正在運作的伺服器數量加 1
        cnt = [0] * (n+1)

        # 依照時間順序讀取查詢，用滑動視窗更新範圍內的伺服器請求狀況，再更新答案
        ans = [0] * len(queries)  # 每個詢問的答案
        left, right = 0, 0  # 視窗左端點
        active = 0  # 正在工作的伺服器數量
        for t, query in sorted_queries:
            # 新增時刻小於、等於 t 的請求
            while right < m and logs[right][1] <= t:
                server = logs[right][0]  # 伺服器編號
                if cnt[server] == 0:  # server 原來沒有請求
                    active += 1  # 正在工作的伺服器數量加 1
                cnt[server] += 1
                right += 1
            
            # 移除時刻小於 t - x 的請求
            while left < right and logs[left][1] < t - x:
                server = logs[left][0]  # 伺服器編號
                if cnt[server] == 1:  # server 原來的請求數量為 1
                    active -= 1  # 正在工作的伺服器數量加 1
                cnt[server] -= 1
                left += 1
            
            # 更新 ans
            ans[query] = n - active
        
        return ans

C++ 程式碼

Runtime: 47 ms, beats 77.49%. Memory: 201.87 MB, beats 72.73%.

class Solution {
public:
    vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
        // 將詢問及原始的索引值組成 pair，再依照時刻排序
        int d = queries.size();  // d 次查詢
        vector<pair<int, int>> sorted_queries;
        for(int i = 0; i < d; i++) {
            sorted_queries.push_back({queries[i], i});
        }
        sort(sorted_queries.begin(), sorted_queries.end());
        
        // logs 依照時刻排序
        int m = logs.size();  // m 次請求
        sort(logs.begin(), logs.end(), [] (const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        } );
        
        // 用 cnt 記錄伺服器收到的請求數量，如果某個伺服器的請求數量由 0 變成 1，正在運作的伺服器數量加 1
        vector<int> cnt (n+1, 0);

        // 依照時間順序讀取查詢，用滑動視窗更新範圍內的伺服器請求狀況，再更新答案
        vector<int> ans (d, 0);  // 每個詢問的答案
        int left = 0, right = 0, active = 0;  // 視窗左端點、右端點，正在工作的伺服器數量
        for(auto it : sorted_queries) {
            int t = it.first, query = it.second;
            // 新增時刻小於、等於 t 的請求
            while(right < m && logs[right][1] <= t) {
                int server = logs[right][0];  // 伺服器編號
                if (cnt[server] == 0) {  // server 原來沒有請求
                    active++;  // 正在工作的伺服器數量加 1
                }
                cnt[server]++;
                right++;
            }
            
            // 移除時刻小於 t - x 的請求
            while(left < right && logs[left][1] < t - x) {
                int server = logs[left][0];  // 伺服器編號
                if (cnt[server] == 1) {  // server 原來的請求數量為 1
                    active--;  // 正在工作的伺服器數量加 1
                }
                cnt[server]--;
                left++;
            }

            // 更新 ans
            ans[query] = n - active;
        }        
        return ans;
    }
};