how to overlap intervals efficiently

Question

I require your help, I have a problem (see picture), I have let say two arrays and each of this array contains intervals with different length and real values and I need to find out how I'm gone overlap this intervals efficiently.

I'm open to ideas, or paper theory or concret algorithms which will let me find a way out! I'm guessing about to transform this somehow in waves and overlap them.

Its very important, its for my thesis.

as an example, here in numbers to explain it better:

1. Array: 1-2, 5-7, 9-12
2. Array: 3-4, 5-6, 13-17

The result will be then one single array containing the new intervals.

second interval (Array one and two) are overlapped.

result Array: 1-2, 3-4, 5-7, 9-12, 13-17

I'm thinking about "interval tree", but its not sufficent how I'm gone merge them.

Thanks in advance!

Answer 1

1) Put all of your intervals in one array.

2) Sort that array by the lower bound of each interval.

3) Loop through the intervals from lowest lower bound to highest upper bound:

a) If the interval after this one starts before this one ends, merge them (delete the second one and extend this one to have its upper bound).

b) Repeat until the next interval starts after this one ends.

4) Repeat until you've reached the last interval.