如何有效地重叠间隔

Question

我需要你的帮助,我有一个问题(见图),我已经说过两个数组,每个数组都包含不同长度和实际值的区间,我需要找出我是如何有效地重叠这个区间的.

我对创意,纸质理论或混凝土算法持开放态度,让我找到出路!我猜想要以某种方式在波浪中改变它并重叠它们.

它非常重要,它适用于我的论文.

作为一个例子,这里有数字来解释它更好:

1. 阵列:1-2,5-7,9-12
2. 阵列:3-4,5-6,13-​​17

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

第二个间隔(第一个和第二个)重叠.

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

我正在考虑"间隔树",但它不足以让我如何合并它们.

提前致谢!

Answer 1

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

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

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

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

b)重复此操作结束后重复下一个间隔.

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