Merge Intervals

Given a list of intervals, merge every overlapping interval. Input format: - First line: n - Next n lines: start end Print merged intervals sorted by start, one interval per line as `start end`.

1 <= n <= 10^5
-10^9 <= start <= end <= 10^9

4
1 3
2 6
8 10
15 18

1 6
8 10
15 18

2
1 4
4 5

1 5