给定两个排序的间隔列表，返回两个列表之间的重叠间隔

给你两个间隔列表，A and B.

In A，间隔按其起点排序。没有任何区间在A重叠。

同样，在B，间隔按其起点排序。没有任何区间在B重叠。

返回两个列表之间重叠的间隔。

Example:

A: {[0,4], [7,12]}
B: {[1,3], [5,8], [9,11]}

Return:

{[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] 时） - 如果此类间隔不应该给出交集，则在打开事件之前处理结束事件