← 返回 bytedance 的题目列表Merge Intervals with Possibly Reversed Endpoints
类型：online_judge
Problem: Merge Intervals with Possibly Reversed Endpoints
You are given n intervals, where each interval is represented by two integers [start, end]. Because the data source may be inconsistent, an interval may have start > end. In that case, you should first normalize it as [end, start].
Merge all overlapping intervals and output the merged intervals sorted by their start values.
Two intervals [a, b] and [c, d] are considered overlapping or touching if c <= b, and they should be merged into [a, max(b, d)].
Input Format
The first line contains an integer n, the number of intervals.
The next n lines each contain two integers start end, representing one interval.
Output Format
The first line should contain an integer k, the number of merged intervals.
The next k lines should each contain two integers representing a merged interval [start, end].
The merged intervals must be sorted by start in ascending order.
Constraints
0 <= n <= 2 * 10^5
-10^9 <= start, end <= 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:
4
5 1
2 3
10 8
9 12
Output:
2
1 5
8 12
Example
Input
4
1 3
2 6
8 10
15 18
Output
3
1 6
8 10
15 18