给定A
和B
,这是两个区间列表。 A
在 A
内部没有重叠,B
在 B
内部没有重叠。在 A
中,间隔按其起点排序。在 B
中,间隔按其起点排序。如何合并两个区间列表并输出不重叠的结果?
一种方法是连接两个列表,按起点排序,并应用合并间隔,如 https://www.geeksforgeeks.org/merging-intervals/ 中所述。 .有没有更有效的方法?
这是一个例子:
A: [1,5], [10,14], [16,18]
B: [2,6], [8,10], [11,20]
输出:
[1,6], [8, 20]
最佳答案
因此您有两个包含事件的排序列表 - 进入间隔和离开间隔。
合并这些列表,将当前状态保持为整数 0、1、2(事件间隔计数)
Get the next coordinate from both lists
If it is entering event
Increment state
If state becomes 1, start new output interval
If it is closing event
Decrement state
If state becomes 0, close current output interval
请注意,此算法类似于求交集 there
关于algorithm - 合并两个排序的间隔列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49583752/