← 返回 google 的题目列表Intervals with a Target Meeting Concurrency
类型：online_judge
Problem: Intervals with a Target Meeting Concurrency
You are given M meeting intervals. Meeting i is represented as a half-open interval [start_i, end_i): it starts at start_i and ends at end_i.
You are also given an integer X. Output every maximal continuous time interval during which exactly X meetings are in progress.
A meeting ending at time t is not active after t; a meeting starting at t is active after t.
Therefore, a meeting ending at t and another starting at t do not overlap.
Output non-empty half-open intervals [l, r) in ascending order of start time.
Adjacent qualifying intervals must be merged.
Input Format
First line: two integers M X
Next M lines: two integers start_i end_i
Output Format
First output the number K of qualifying intervals.
Then output K lines, each containing l r for an interval [l, r).
Constraints
1 <= M <= 2 * 10^5
1 <= X <= M
0 <= start_i < end_i <= 10^9
Example
Input
3 2
1 5
2 6
5 8
Output
1
2 6
Example
Input
3 2
1 5
2 6
5 8
Output
1
2 6