如何有效地重叠间隔 [英] 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. 数组:1-2、5-7、9-12
2. 数组:3-4、5-6、13-17

结果将是一个包含新间隔的单个数组.

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

第二个时间间隔(数组1和2)重叠.

second interval (Array one and two) are overlapped.

结果数组:1-2、3-4、5-7、9-12、13-17

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.

提前谢谢！

推荐答案

1)将所有间隔放入一个数组中.

1) Put all of your intervals in one array.

2)按每个间隔的下限对该数组进行排序.

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

3)循环遍历从最低下限到最高上限的间隔:

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

a)如果此间隔之后的间隔在此间隔结束之前开始，则将它们合并(删除第二个间隔并扩展此间隔以使其具有上限).

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)重复，直到此间隔结束后下一个间隔开始.

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

4)重复直到到达最后一个间隔.

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

这篇关于如何有效地重叠间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！