Merge all overlapping intervals. Intervals that only touch ([1, 4] and [4, 5]) also merge.
Input
The first line has n (1 ≤ n ≤ 10⁵). Each of the next n lines has an interval start end (start ≤ end).
Output
The merged intervals in increasing order, one per line, as start end.
Examples
Example 1 · Input
4 1 3 2 6 8 10 15 18
Expected output
1 6 8 10 15 18
Example 2 · Input
2 1 4 4 5
Expected output
1 5
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Sort the intervals by their start.
Hint 2
If the next interval starts at or before the end of the last merged one, they overlap: extend the end.
Hint 3
Use max for the end: one interval can be inside another.
Solution
Show one correct solution (try it yourself first)
n = int(input())
intervals = sorted(tuple(map(int, input().split())) for _ in range(n))
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
for start, end in merged:
print(start, end)