Insert Interval

Given a list of already-sorted, non-overlapping intervals and a new interval, insert it and merge if necessary.

Example

Input: existing [1,3] [6,9], new [2,5] Output: [1,5] [6,9]

Approach

Three passes in one sweep: first copy every interval that ends before the new one starts (no overlap, untouched), then absorb every interval that overlaps the new one by expanding the new interval's own start/end to cover them, then copy the remaining intervals that start after the (now-expanded) new interval ends.

Input format

Line 1: number of existing intervals R Next R lines: start end Last line: the new interval, start end

Print the result, one start end pair per interval, separated by |.