Description#
You are given an integer n denoting the total number of servers and a 2D 0-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 a 0-indexed integer array arr of length queries.length where arr[i] represents the number of servers that did not receive any requests during the time interval [queries[i] - x, queries[i]].
Note that the time intervals are inclusive.
Example 1:
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.
Example 2:
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].
Constraints:
1 <= n <= 1051 <= logs.length <= 1051 <= queries.length <= 105logs[i].length == 21 <= logs[i][0] <= n1 <= logs[i][1] <= 1061 <= x <= 105x < queries[i] <= 106
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def countServers(
self, n: int, logs: List[List[int]], x: int, queries: List[int]
) -> List[int]:
cnt = Counter()
logs.sort(key=lambda x: x[1])
ans = [0] * len(queries)
j = k = 0
for r, i in sorted(zip(queries, count())):
l = r - x
while k < len(logs) and logs[k][1] <= r:
cnt[logs[k][0]] += 1
k += 1
while j < len(logs) and logs[j][1] < l:
cnt[logs[j][0]] -= 1
if cnt[logs[j][0]] == 0:
cnt.pop(logs[j][0])
j += 1
ans[i] = n - len(cnt)
return ans
|
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
| class Solution {
public int[] countServers(int n, int[][] logs, int x, int[] queries) {
Arrays.sort(logs, (a, b) -> a[1] - b[1]);
int m = queries.length;
int[][] qs = new int[m][0];
for (int i = 0; i < m; ++i) {
qs[i] = new int[] {queries[i], i};
}
Arrays.sort(qs, (a, b) -> a[0] - b[0]);
Map<Integer, Integer> cnt = new HashMap<>();
int[] ans = new int[m];
int j = 0, k = 0;
for (var q : qs) {
int r = q[0], i = q[1];
int l = r - x;
while (k < logs.length && logs[k][1] <= r) {
cnt.merge(logs[k++][0], 1, Integer::sum);
}
while (j < logs.length && logs[j][1] < l) {
if (cnt.merge(logs[j][0], -1, Integer::sum) == 0) {
cnt.remove(logs[j][0]);
}
j++;
}
ans[i] = n - cnt.size();
}
return ans;
}
}
|
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
| class Solution {
public:
vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
sort(logs.begin(), logs.end(), [](const auto& a, const auto& b) {
return a[1] < b[1];
});
int m = queries.size();
vector<pair<int, int>> qs(m);
for (int i = 0; i < m; ++i) {
qs[i] = {queries[i], i};
}
sort(qs.begin(), qs.end());
unordered_map<int, int> cnt;
vector<int> ans(m);
int j = 0, k = 0;
for (auto& [r, i] : qs) {
int l = r - x;
while (k < logs.size() && logs[k][1] <= r) {
++cnt[logs[k++][0]];
}
while (j < logs.size() && logs[j][1] < l) {
if (--cnt[logs[j][0]] == 0) {
cnt.erase(logs[j][0]);
}
++j;
}
ans[i] = n - cnt.size();
}
return ans;
}
};
|
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
| func countServers(n int, logs [][]int, x int, queries []int) []int {
sort.Slice(logs, func(i, j int) bool { return logs[i][1] < logs[j][1] })
m := len(queries)
qs := make([][2]int, m)
for i, q := range queries {
qs[i] = [2]int{q, i}
}
sort.Slice(qs, func(i, j int) bool { return qs[i][0] < qs[j][0] })
cnt := map[int]int{}
ans := make([]int, m)
j, k := 0, 0
for _, q := range qs {
r, i := q[0], q[1]
l := r - x
for k < len(logs) && logs[k][1] <= r {
cnt[logs[k][0]]++
k++
}
for j < len(logs) && logs[j][1] < l {
cnt[logs[j][0]]--
if cnt[logs[j][0]] == 0 {
delete(cnt, logs[j][0])
}
j++
}
ans[i] = n - len(cnt)
}
return ans
}
|
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
| function countServers(n: number, logs: number[][], x: number, queries: number[]): number[] {
logs.sort((a, b) => a[1] - b[1]);
const m = queries.length;
const qs: number[][] = [];
for (let i = 0; i < m; ++i) {
qs.push([queries[i], i]);
}
qs.sort((a, b) => a[0] - b[0]);
const cnt: Map<number, number> = new Map();
const ans: number[] = new Array(m);
let j = 0;
let k = 0;
for (const [r, i] of qs) {
const l = r - x;
while (k < logs.length && logs[k][1] <= r) {
cnt.set(logs[k][0], (cnt.get(logs[k][0]) || 0) + 1);
++k;
}
while (j < logs.length && logs[j][1] < l) {
cnt.set(logs[j][0], (cnt.get(logs[j][0]) || 0) - 1);
if (cnt.get(logs[j][0]) === 0) {
cnt.delete(logs[j][0]);
}
++j;
}
ans[i] = n - cnt.size;
}
return ans;
}
|
