An API gateway limits traffic using FIXED time windows of length w seconds: window 0 covers [0, w), window 1 covers [w, 2w), and so on. At most m requests may be admitted within any single fixed window; every request beyond the first m admitted requests within a window is rejected (dropped), and a rejected request does not count toward any window's quota.
You are given n requests' arrival timestamps (non-negative integers, seconds since start, given in non-decreasing order). For each request, its window index is floor(timestamp / w). Process requests in the given order: a request is admitted if the number of already-admitted requests in its window is strictly less than m; otherwise it is rejected.
Print the total number of admitted requests.
Line 1: three integers n, w, m.
Line 2: n space-separated non-decreasing integers, the request timestamps.
A single integer: the total number of admitted requests.
Example 1
Input
5 10 2 0 1 5 11 12
Expected
4
Explanation
Window 0 covers [0,10) and admits t=0 and t=1 (2 slots used), so t=5 is rejected. Window 1 covers [10,20) and admits both t=11 and t=12, for 4 admitted requests total.
Example 2
Input
3 5 1 0 0 0
Expected
1
Explanation
All three requests fall in window 0, which allows only 1 admission, so only the first request is admitted.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →