Array
Hash Table
Sorting
Sliding Window
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 <= 105
1 <= logs.length <= 105
1 <= queries.length <= 105
logs[i].length == 2
1 <= logs[i][0] <= n
1 <= logs[i][1] <= 106
1 <= x <= 105
x < queries[i] <= 106
Solutions
Solution 1
Python3 Java C++ Go TypeScript
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 ;
}
GitHub