2747. Count Zero Request Servers

Time: O(m log m + q log q)

Space: O(n + q)

Problem Overview

Each query asks how many servers received no request in the closed interval from the query time minus x through the query time.

Intuition

Each query asks how many servers received no request in the closed interval from the query time minus x through the query time. Scanning every log for every query is too slow once both lists reach length 100000. Sorting the logs by time and the queries by time lets one window slide forward. The right pointer adds every log whose time is at most the current query. The left pointer drops every log whose time is strictly before the query minus x, so a log that lands on the left endpoint stays inside the inclusive interval. A count array stores how many logs each server still has in the window. A server becomes active when its count rises from 0 to 1, and it leaves when the count falls back to 0. The idle count is n minus the number of active servers. Each query is packed with its original index, so the answers are written back in the input order.

Algorithm

1Pack each query time with its original index and sort those values. Sort the logs by time.
2Keep a count for every server and a count of servers that appear at least once in the window.
3For each query in time order, advance the right pointer through logs at or before the query time.
4Advance the left pointer through logs that fall before the query time minus x.
5Store n minus the active server count at the original query index, then return that array.

Example Walkthrough

Input: n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]

1.Query 10 covers times 5 through 10. Server 1 logged at 5 and server 2 logged at 6.
2.Server 3 has no log in that window, so one server is idle.
3.Query 11 covers times 6 through 11. The log at time 5 has left, only server 2 remains, and two servers are idle.

Output: [1, 2]

Common Pitfalls

•The window is closed on both ends. A log at time query minus x stays, and a log at the query time stays.
•Drop a server from the active count only when its own count returns to 0. One server can have several logs in the same window.
•Write each answer at the original query index. The queries are processed in time order.
•Server ids run from 1 through n. The count array has a slot for each of them.

2747.cs

// Approach: A server is idle for a query when it has no log in the closed
// interval from the query time minus x through the query time. Sorting the
// logs by time and the queries by time lets two pointers slide that window.
// A count array tracks how many logs each server has inside the window.
// The answer is n minus the number of servers whose count is positive.
// Time: O(m log m + q log q) Space: O(n + q)

public class Solution {
    public int[] CountServers(int n, int[][] logs, int x, int[] queries) {
        int qLen = queries.Length;
        long[] order = new long[qLen];
        for (int i = 0; i < qLen; i++)
            order[i] = ((long)queries[i] << 32) | (uint)i;
        Array.Sort(order);
        Array.Sort(logs, (a, b) => a[1].CompareTo(b[1]));

        int[] ans = new int[qLen];
        int[] count = new int[n + 1];
        int left = 0, right = 0, active = 0;
        for (int i = 0; i < qLen; i++) {
            int end = (int)(order[i] >> 32);
            int index = (int)order[i];
            int start = end - x;

            while (right < logs.Length && logs[right][1] <= end) {
                if (++count[logs[right][0]] == 1)
                    active++;
                right++;
            }
            while (left < logs.Length && logs[left][1] < start) {
                if (--count[logs[left][0]] == 0)
                    active--;
                left++;
            }
            ans[index] = n - active;
        }
        return ans;
    }
}

Was this solution helpful?