Merge Overlapping Intervals
Mediumjavapythonccppjavascript
Given a collection of intervals, merge all intervals that overlap or touch, and print the result sorted by start value.
Input Format
The first line contains an integer N, the number of intervals. Each of the next N lines contains two integers start and end (start <= end).
Output Format
Print the merged intervals, one per line as start end, in increasing order of start.
Example 1
Input
4 1 3 2 6 8 10 9 12
Output
1 6 8 12
Explanation: [1,3] overlaps [2,6] -> [1,6]; [8,10] overlaps [9,12] -> [8,12].
- 1 <= N <= 100000
- -1000000000 <= start <= end <= 1000000000
- Two intervals are merged when one's start is <= the other's end.