You are given an integer n denoting the total number of servers and a 2D0-indexed integer array logs, where logs[i] = [server_id, time]
denotes that the server with id server_id received a request at time time.
You are also given an integer x and a 0-indexed integer array queries.
Return a0-indexed integer arrayarrof lengthqueries.lengthwherearr[i]represents the number of servers thatdid not receive any requests during the time interval[queries[i] - x, queries[i]].
Input: n =3, logs =[[1,3],[2,6],[1,5]], x =5, queries =[10,11]Output: [1,2]Explanation:
For queries[0]: The servers with ids 1 and 2 get requests in the duration of [5,10]. Hence, only server 3 gets zero requests.For queries[1]: Only the server with id 2 gets a request in duration of [6,11]. Hence, the servers with ids 1 and 3 are the only servers that do not receive any requests during that time period.
Input: n =3, logs =[[2,4],[2,1],[1,2],[3,1]], x =2, queries =[3,4]Output: [0,1]Explanation:
For queries[0]: All servers get at least one request in the duration of [1,3].For queries[1]: Only server with id 3 gets no request in the duration [2,4].
The key idea is to use a sliding window over the sorted logs to efficiently count, for each query, which servers did not receive any requests in the interval [query - x, query]. By sorting both logs and queries, we can process all queries in a single pass using two pointers and a hash map to track the number of requests per server in the current window.
classSolution {
publicint[]countServers(int n, int[][] logs, int x, int[] queries) {
Arrays.sort(logs, Comparator.comparingInt(a -> a[1]));
int m = queries.length;
int[][] qs =newint[m][2];
for (int i = 0; i < m; i++) {
qs[i][0]= queries[i];
qs[i][1]= i;
}
Arrays.sort(qs, Comparator.comparingInt(a -> a[0]));
int[] cnt =newint[n+1];
int[] ans =newint[m];
int l = 0, r = 0, active = 0;
for (int[] q : qs) {
int query = q[0], idx = q[1];
while (r < logs.length&& logs[r][1]<= query) {
int id = logs[r][0];
if (++cnt[id]== 1) active++;
r++;
}
while (l < logs.length&& logs[l][1]< query - x) {
int id = logs[l][0];
if (--cnt[id]== 0) active--;
l++;
}
ans[idx]= n - active;
}
return ans;
}
}
classSolution {
funcountServers(n: Int, logs: Array<IntArray>, x: Int, queries: IntArray): IntArray {
logs.sortBy { it[1] }
val qs = queries.mapIndexed { i, q -> q to i }.sortedBy { it.first }
val cnt = IntArray(n+1)
val ans = IntArray(queries.size)
var l = 0; var r = 0; var active = 0for ((q, idx) in qs) {
while (r < logs.size && logs[r][1] <= q) {
val id = logs[r][0]
if (++cnt[id] ==1) active++ r++ }
while (l < logs.size && logs[l][1] < q - x) {
val id = logs[l][0]
if (--cnt[id] ==0) active-- l++ }
ans[idx] = n - active
}
return ans
}
}
classSolution:
defcountServers(self, n: int, logs: list[list[int]], x: int, queries: list[int]) -> list[int]:
logs.sort(key=lambda a: a[1])
qs = sorted([(q, i) for i, q in enumerate(queries)])
cnt = [0] * (n+1)
ans = [0] * len(queries)
l = r = active =0for q, idx in qs:
while r < len(logs) and logs[r][1] <= q:
id = logs[r][0]
cnt[id] +=1if cnt[id] ==1:
active +=1 r +=1while l < len(logs) and logs[l][1] < q - x:
id = logs[l][0]
cnt[id] -=1if cnt[id] ==0:
active -=1 l +=1 ans[idx] = n - active
return ans
⏰ Time complexity: O((L + Q) log L + L + Q + n), where L is the number of logs, Q is the number of queries, and n is the number of servers. Sorting dominates.
🧺 Space complexity: O(n + Q), for the count array and answer array.