← 返回 uber 的题目列表Insert Interval / Merge Intervals with a New Interval
类型：online_judge
Problem
You are given a list of non-overlapping intervals intervals sorted by start time, and a new interval newInterval. Insert newInterval into intervals so that the result remains sorted by start time and merge all overlapping intervals.
Intervals are closed intervals [start, end].
Input
First line: integer n, the number of intervals.
Next n lines: two integers start end.
Last line: two integers s e representing newInterval = [s, e].
Output
Print k, the number of intervals after insertion and merging.
Then print k lines of merged intervals in ascending order.
Constraints
0 <= n <= 2 * 10^5
-10^9 <= start <= end <= 10^9
intervals is initially sorted by start and pairwise non-overlapping.
Example
Input:
2
1 3
6 9
2 5
Output:
2
1 5
6 9
Example
Input
0
2 5
Output
1
2 5