← 返回 amazon 的题目列表Merge Intervals
类型：online_judge
Problem: Merge Intervals
Given an array of intervals intervals, where intervals[i] = [start_i, end_i], merge all overlapping intervals and return a non-overlapping list of intervals that covers all intervals in the input.
Two intervals [a, b] and [c, d] are considered overlapping if c <= b, and they can be merged into [min(a, c), 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 and end, representing one interval.
Output Format
Output the merged intervals sorted by start point.
Each line contains two integers representing one merged interval.
Constraints
0 <= n <= 10^5
-10^9 <= start_i <= end_i <= 10^9
Example
Input:
4
1 3
2 6
8 10
15 18
Output:
1 6
8 10
15 18
Example
Input
4
1 3
2 6
8 10
15 18
Output
1 6
8 10
15 18