<p>You are given an integer <code>n</code> denoting the total number of servers and a <strong>2D</strong> <strong>0-indexed </strong>integer array <code>logs</code>, where <code>logs[i] = [server_id, time]</code> denotes that the server with id <code>server_id</code> received a request at time <code>time</code>.</p>

<p>You are also given an integer <code>x</code> and a <strong>0-indexed</strong> integer array <code>queries</code>.</p>

<p>Return <em>a <strong>0-indexed</strong> integer array</em> <code>arr</code> <em>of length</em> <code>queries.length</code> <em>where</em> <code>arr[i]</code> <em>represents the number of servers that <strong>did not receive</strong> any requests during the time interval</em> <code>[queries[i] - x, queries[i]]</code>.</p>

<p>Note that the time intervals are inclusive.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
<strong>Output:</strong> [1,2]
<strong>Explanation:</strong> 
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.

</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]
<strong>Output:</strong> [0,1]
<strong>Explanation:</strong> 
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].

</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= logs.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code><font face="monospace">logs[i].length == 2</font></code></li>
	<li><code>1 &lt;= logs[i][0] &lt;= n</code></li>
	<li><code>1 &lt;= logs[i][1] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= x &lt;= 10<sup>5</sup></code></li>
	<li><code>x &lt;&nbsp;queries[i]&nbsp;&lt;= 10<sup>6</sup></code></li>
</ul>

'''
HCT
14:58 - 15:18: Think
15:18 - 15:30: Code

SLIDING WINDOW
1. Brute force:
    for q in queries:
        cnt = 0
        counted = defaultdict(int)
        for server, time in logs:
            if time in [q - X, q] and server not in counted:
                cnt += 1
                counted[server] = 1

    => O(len(queries) * len(logs)) => TLE
    => How can optimise?
        - Optimise the inner loop st we dont need to re-loop from the beginning of logs for each query => re-use the result of previous query
        - For ex: 
            +) queries[0] = 10 -> need count #servers in [5, 10] = 2
               queries[1] = 11 -> need count #servers in [6, 11] = [5,10] - [5,6] + [10,11] -> if assume [5,10] is the current window, so we need to expand its right side by 1, and shrink its left side by 1.
        - So apply dynamic sliding window technique to optimise the inner loop. But how can we re-use the previous query result conveniently? => Sort the queries list, and mapped the index correspondingly
        - Also, sort the 'logs' list based on time, st we can expand/shrink the window in time increasingly

#2. Optimise
1.   Sort query (map), logs(based on time)
2.   For each query, expand the right side of our current window as long as logs[r][1] <= queryTime
     Also, shrink the left side of our current window until logs[l][1] >= queryTime - X
3.   So now, how could we count #distinct_servers in this window[l..r]? => using a hashmap to existed server, and 1 variable servers to count

Time complexity: O(m + logSize) + O(logSize*log(logSize)) + O(mlogm)
Space complexity: O(m + n + logSize)
'''

class Solution:
    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
        logs.sort(key=lambda log: log[1])
        queries = sorted(enumerate(queries), key=lambda q: q[1])
        
        activeServers = Counter()
        totalActive = 0
        left = right = 0
        results = {}
        
        for queryIndex, queryTime in queries:
            # Add servers that became active before or at the query time
            while right < len(logs) and logs[right][1] <= queryTime:
                server = logs[right][0]
                if activeServers[server] == 0:
                    totalActive += 1
                activeServers[server] += 1
                right += 1
            
            # Remove servers that are no longer active
            while left < right and logs[left][1] < queryTime - x:
                server = logs[left][0]
                activeServers[server] -= 1
                if activeServers[server] == 0:
                    totalActive -= 1
                left += 1
            
            results[queryIndex] = n - totalActive
        
        return [results[i] for i in range(len(queries))]
78700