你有两个区间列表，A 和 B。
在 A 中，间隔按其起点排序。 A 中的所有间隔都没有重叠。
同样，在 B 中，间隔按其起点排序。 B 中的所有区间都不重叠。
返回两个列表之间重叠的区间。
例子:
A: {[0,4], [7,12]}
B: {[1,3], [5,8], [9,11]}
返回:
{[1,3], [7,8], [9,11]}
我在一次采访中得到了这个并且被难住了。
我想到了比较两个列表之间的间隔。如果两者之间存在重叠，则将重叠添加到结果列表中。然后我用较小的起始间隔推进列表的指针，但在采访结束时无法找到可行的解决方案。
解决这个问题的最佳方法是什么？
最佳答案
因此您有两个包含事件的列表 - 进入间隔和离开间隔。合并这些列表，将当前状态保持为整数 0、1、2(事件间隔计数)
Get the next coordinate from both lists
If it is entering event
Increment state
If state becomes 2, start new output interval
If it is closing event
Decrement state
If state becomes 1, close current output interval
根据所选规则处理关系(当值等于 [0..1] 和 [1..2] 时)- 如果此类间隔不应给出交集，则在打开事件之前处理关闭事件
关于algorithm - 给定两个排序的区间列表，返回两个列表之间的重叠区间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49583104/