You are given a 2D integer array requests, where requests[i] = [useri, timei] indicates that useri made a request at timei.
You are also given two integers k and window.
A user violates the limit if there exists an integer t such that the user makes strictly more than k requests in the inclusive interval [t, t + window].
You may drop any number of requests.
Return an integer denoting the maximum number of requests that can remain such that no user violates the limit.
Example 1:
Input: requests = [[1,1],[2,1],[1,7],[2,8]], k = 1, window = 4
Output: 4
Explanation:
[1, 7]. The difference between them is 6, which is greater than window = 4.[1, 8]. The difference is 7, which is also greater than window = 4.k = 1 request within any inclusive interval of length window. Therefore, all 4 requests can remain.Example 2:
Input: requests = [[1,2],[1,5],[1,2],[1,6]], k = 2, window = 5
Output: 2
Explanation:
[2, 2, 5, 6]. The inclusive interval [2, 7] of length window = 5 contains all 4 requests.k = 2, at least 2 requests must be removed.window contains at most k = 2 requests.Example 3:
Input: requests = [[1,1],[2,5],[1,2],[3,9]], k = 1, window = 1
Output: 3
Explanation:
[1, 2]. The difference is 1, which is equal to window = 1.[1, 2] contains both requests, so the count is 2, which exceeds k = 1. One request must be removed.Constraints:
1 <= requests.length <= 105requests[i] = [useri, timei]1 <= k <= requests.length1 <= useri, timei, window <= 105Loading editor...
[[1,1],[2,1],[1,7],[2,8]] 1 4