overlap - 如何有效地重叠间隔

Question

我需要你的帮助，我有一个问题(见图)，我假设有两个数组，每个数组都包含不同长度和实际值的间隔，我需要找出我如何有效地重叠这些间隔。

我对想法、论文理论或具体算法持开放态度，它们会让我找到出路!
我猜想以某种方式在波浪中转换它并重叠它们。

它非常重要，它对于我的论文。

例如，这里用数字来更好地解释它:

数组:1-2、5-7、9-12

数组:3-4、5-6、13-17

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

第二个间隔(数组一和二)重叠。

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

我正在考虑“间隔树”，但我如何将它们合并还不够。

提前致谢!

Answer 1

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

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

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

a) 如果这一个之后的区间在这一个结束之前开始，则合并它们(删除第二个并扩展这个有其上界)。

b) 重复直到此间隔结束后下一个间隔开始。

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