2747. Count Zero Request Servers

2026, Nov 05 2 mins read

1. Description

There are n servers numbered 1 through n. Each record logs[i] = [server, time] indicates that the given server received a request at that time.
Given an integer x and an array queries, count the servers with no requests in [queries[i] - x, queries[i]] for each query. Both endpoints are included.
Return the counts in the original query order.

2. Example

Example 1

Input: n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
Output: [1,2]
Explanation: In [5,10], servers 1 and 2 are active, leaving only server 3 idle. In [6,11], only server 2 is active, so two servers are idle.

Example 2

Input: n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]
Output: [0,1]
Explanation: Every server receives a request in [1,3]. In [2,4], only server 3 receives no requests.

3. Constraints

1 <= n <= 10$^5$
1 <= logs.length <= 10$^5$
1 <= queries.length <= 10$^5$
logs[i].length == 2
1 <= logs[i][0] <= n
1 <= logs[i][1] <= 10$^6$
1 <= x <= 10$^5$
x < queries[i] <= 10$^6$

4. Solutions

Offline Queries with Sliding Window

n = number of servers, m = logs.size(), o = queries.size()
Time complexity: O(n + m log m + o log o)
Space complexity: O(n + o + log m)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    vector<int> countServers(int n, vector<vector<int>> &logs, int x, vector<int> &queries) {
        const int m = logs.size(), o = queries.size();
        sort(logs.begin(), logs.end(), [](const vector<int> &a, const vector<int> &b) {
            return a[1] < b[1];
        });

        vector<pair<int, int>> sorted_queries;
        for (int i = 0; i < o; ++i) {
            sorted_queries.emplace_back(queries[i], i);
        }
        sort(sorted_queries.begin(), sorted_queries.end());

        int left = 0, right = 0;
        vector<int> request_count(n + 1, 0);
        int server = 0;
        vector<int> result(o, 0);

        for (const auto &[query, index] : sorted_queries) {
            while (right < m && logs[right][1] <= query) {
                if (request_count[logs[right][0]] == 0) {
                    ++server;
                }

                ++request_count[logs[right][0]];
                ++right;
            }

            while (left < right && logs[left][1] < query - x) {
                if (request_count[logs[left][0]] == 1) {
                    --server;
                }

                --request_count[logs[left][0]];
                ++left;
            }

            result[index] = n - server;
        }

        return result;
    }
};

Search

Tags