1436. Inserting an Interval
You are given n intervals, already sorted by start and with no two
overlapping, and one new interval. Insert it and merge anything it overlaps,
then print the resulting list.
Intervals touching at a boundary count as overlapping, so [1,3] and [3,5]
become [1,5].
One pass in three phases: copy every interval that ends before the new one starts, absorb every interval that overlaps by widening the new one to the extremes of both, then copy the rest.
Re-sorting and running a general merge also works and does more than the sorted input requires.
Constraints - `0 ≤ n ≤ 100000` - `-1000000000 ≤ start ≤ end ≤ 1000000000` - The given intervals are sorted and non-overlapping.
Input
The first line contains an integer n.
Each of the next n lines contains two integers: the start and end of one interval.
The last line contains two integers: the start and end of the interval to insert.
Output
Print the resulting intervals, one per line, each as two space-separated integers, in increasing order of start.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.