← 返回 snapchat 的题目列表Max Unique Users in Any Time Window
类型：online_judge
Given an event list events, each event contains:
timestamp: an integer timestamp
user_id: a user identifier (integer or string)
You are also given a window size W (integer). For any time window [t, t+W), the window contains all events with t <= timestamp < t+W.
Compute the maximum number of unique user_ids that appear in any such time window.
Notes:
Multiple events from the same user_id within the same window count only once.
Output a single integer: the maximum unique user count.
Input (stdin)
First line: two integers n W
Next n lines: timestamp user_id
Output (stdout)
One line: the maximum unique user count
Constraints
1 <= n <= 2*10^5
0 <= timestamp <= 10^9
W >= 0
user_id is a non-space string (you may treat it as a string)
Example
Input:
6 10
0 1
3 2
4 1
10 3
11 2
19 4
Output:
3
Explanation: window [3,13) contains unique users {1,2,3} so the answer is 3.
Example
Input
6 10
0 1
3 2
4 1
10 3
11 2
19 4
Output
3