Max Events in Any 60-Second Window

The venue meters your session: no more than a fixed number of messages in any 60-second window, and a breach disconnects you mid-trade. The gateway logs the time of every message it sends, so the question after a busy day is simple. What was the most messages this session put through any one window?

The log is a list of integer timestamps in seconds, already sorted in non-decreasing order (two messages in the same second share a timestamp). A window is a half-open interval \([t, t + w)\): a message at exactly \(t + w\) belongs to the next window, not this one. The window may start at any time, not only at a message.

Implement max_events_in_window(timestamps, window) returning the largest number of timestamps that fall inside some window of length window. An empty list returns 0.

Examples

max_events_in_window([0, 10, 20, 70, 80], 60)
# 3  (the window [0, 60) holds 0, 10 and 20)

max_events_in_window([5, 5, 30, 64, 65, 100], 60)
# 4  (the window [5, 65) holds 5, 5, 30 and 64; 65 is outside it)

Constraints

• Up to \(2 \times 10^6\) timestamps with 0 <= timestamps[i] <= 10^9, sorted in non-decreasing order. Timestamps may repeat.
• window is a positive integer.
• Testing every possible window start against every timestamp is \(O(n^2)\) and will not finish in time on the largest hidden test. The input is sorted; think about what that lets you keep instead of recompute.

In C++

long long max_events_in_window(const std::vector<long long>& timestamps,
                               long long window);

The timestamps come in as a sorted std::vector<long long> and the result is the count.