255. Merge Overlapping Intervals
You are given n intervals as pairs start end, in no particular order.
Merge every group that overlaps or touches, and print the result in increasing
order of start.
[1,3] [2,6] [8,10] -> [1,6] [8,10]
Intervals that merely touch, like [1,4] and [4,5], count as overlapping
and become [1,5].
Unsorted, deciding what overlaps what needs every pair compared. Sorted by start, an interval can only overlap the one currently being built, so a single pass finishes it. That is the pattern this topic keeps returning to: sorting is the cheap step that makes the real step easy.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ start ≤ end ≤ 1000000000`
Input
The first line contains an integer n.
Each of the next n lines contains two integers start and end.
Output
Print the number of merged intervals on the first line.
Then print each merged interval on its own line as start end, in increasing order of start.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.