Merge Overlapping Intervals
MediumPractice library · +20 XPsortingintervals
You are given n closed intervals [l, r]. Merge all intervals that overlap or touch ([1,3] and [3,5] merge into [1,5]) and print the merged intervals sorted by their start.
Input
Line 1: n
Next n lines: l r
Output
The merged intervals, one per line as l r, sorted by l.
Constraints
- 1 <= n <= 200000
- 0 <= l <= r <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB10 hidden tests
Example 1
Input
4 1 3 2 6 8 10 15 18
Output
1 6 8 10 15 18
[1,3] and [2,6] overlap and become [1,6].
Example 2
Input
2 1 4 4 5
Output
1 5
Touching intervals merge.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
4 1 3 2 6 8 10 15 18
Example 2 input
2 1 4 4 5