11
Given a set of intervals: {1-4, 6-7, 10-12} add a new interval: (9,11) so that the final solution is 'merged': Output: {1-4, 6-7, 9-12}. The merger can happen on both sides (low as well as high range).
I saw this question was answered at multiple places, someone even suggested using Interval Tress, but did not explain how exactly they would use it. The only solution I know of is to arrange the intervals in ascending order of their start time and iterating over them and trying to merge them appropriately.
If someone can help me understand how we can use interval trees in this use case, that will be great!
[I have been following interval trees in CLRS book, but they do not talk about merging, all they talk about is insertion and search.]