Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
669 views
in Technique[技术] by (71.8m points)

how to overlap intervals efficiently

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.

picture

Thanks in advance!

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...