← 返回 bytedance 的题目列表Merge Intervals
类型：online_judge
Merge Intervals
Given n closed intervals intervals[i] = [start_i, end_i], merge all overlapping intervals and return a list of non-overlapping intervals sorted by their start positions.
Intervals that touch at an endpoint, such as [1,4] and [4,5], must also be merged into [1,5].
Input Format
First line: an integer n
Next n lines: two integers start end per line, representing [start, end]
Output Format
First line: the number k of merged intervals
Next k lines: one merged interval per line, formatted as start end
Constraints
0 <= n <= 10^5
-10^9 <= start_i <= end_i <= 10^9
Example 1
Input:
4
1 3
2 6
8 10
15 18
Output:
3
1 6
8 10
15 18
Example 2
Input:
2
1 4
4 5
Output:
1
1 5
Example
Input
4
1 3
2 6
8 10
15 18
Output
3
1 6
8 10
15 18