← 返回 twosigma 的题目列表Merge Overlapping Intervals
类型：online_judge
Problem
Given intervals intervals where each interval is [l, r] with l <= r, merge all overlapping intervals and output the merged list sorted by start.
Input (stdin)
Line 1: integer n
Next n lines: two integers l r
Output (stdout)
First line: integer k (# merged intervals)
Next k lines: each merged interval l r
Constraints
0 <= n <= 2*10^5
-10^9 <= l, r <= 10^9
Expected time O(n log n) due to sorting
Examples
Example
Input
4
1 3
2 6
8 10
15 18
Output
3
1 6
8 10
15 18