A college seminar hall has n bookings, each a pair start end (inclusive, in hours). Bookings that overlap or touch should be shown as one block.
Print the merged blocks in order of start time.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ start ≤ end ≤ 10^9
Input and output
- Input
- Line 1: n. Then n lines, each with two integers start ≤ end.
- Output
- Line 1: the number of merged blocks k. Then k lines `start end`, sorted by start.
Examples
Input 1
4
9 11
1 4
3 6
12 13Output
3
1 6
9 11
12 131–4 and 3–6 overlap and become 1–6; the others stay apart.
Input 2
2
5 7
7 9Output
1
5 9Touching bookings (one ends at 7, the next starts at 7) merge into 5–9.
Show hints
- Sort by start time.
- Keep extending the current block while the next booking starts at or before its end.
Show the explanation
Sort the bookings by start. Walk through them keeping the current block [s, e]. If the next booking starts at or before e, the two overlap or touch: extend e to the larger end. Otherwise close the block and start a new one. Sorting dominates at O(n log n).
Original UniCircle question. Last reviewed 22 Oct 2026.