Insert an Interval
A sorted list of DISJOINT intervals is given, plus one new interval. Insert it, merging where necessary, and print the resulting disjoint sorted list.
Input: the first line has N; the next N lines have the sorted disjoint intervals; the last line has the new interval.
Output: the merged interval list, one per line.
Constraints:
- 1 ≤ N ≤ 105
- 0 ≤ endpoints ≤ 107
Sample Tests
Input 1
2 1 3 6 9 2 5
Output 1
1 5 6 9
Input 2
1 1 2 4 5
Output 2
1 2 4 5
Discussion (opens after you solve — no spoilers before)
No comments yet.