← 返回 apple 的题目列表Merge Overlapping Intervals
类型：online_judge
Given a list of closed intervals, merge all overlapping intervals and return the merged interval list.
Input: an array intervals, each interval is [start, end] with start <= end.
After sorting by start, two intervals [a,b] and [c,d] overlap if c <= b, and should be merged into [a, max(b,d)].
Output: the merged intervals sorted by start.
Constraints
1 <= n <= 2 * 10^5
-10^9 <= start <= end <= 10^9
Input format (stdin)
Line 1: integer n
Next n lines: start end
Output format (stdout)
Line 1: integer m (number of merged intervals)
Next m lines: start end
Example Input:
4
1 3
2 6
8 10
15 18
Output:
3
1 6
8 10
15 18
Example
Input
4
1 3
2 6
8 10
15 18
Output
3
1 6
8 10
15 18