这与查找重叠区间有关。我知道如何在给定的区间列表（区间树）中执行此操作。但是我现在手头上有一个区间列表的列表。例如：
[2,6], [7,11]
[1,3], [5,10], [11,13]
[2,5], [6,8]
这个问题的结果应该是
[2,3], [7,8]
我需要做的是找到在所有列表中都共有的区间列表。
我认为这个问题类似于合并 n 个列表。但问题是，我不能对列表进行成对合并。这种方法可能会导致重叠区间的丢失。因此，我需要同时考虑所有列表来合并它们（而不是成对）。
我可以使用区间树。将每个列表的第一个区间插入到区间树中，并找到重叠部分。从树中移除最弱的区间，并插入其中一个列表的下一个区间。我还没有完全弄清楚如何使用这种方法，但似乎这将变得太昂贵了。
有没有有效的算法来从区间的列表列表中找到重叠的区间？
其他信息：
列表内的区间已排序。 它们不重叠并形成一个序列。
[2, 1], [6, -1], [7, 1], [11, -1],
[1, 1], [3, -1], [5, 1], [10, -1], [11, 1], [13, -1]
[2, 1], [5, -1], [6, 1], [8, -1]
经过按位置排序和合并后，变成了：
[1, 1], [2, 2], [3, -1], [5, 0], [6, 0], [7, 1], [8, -1], [10, -1], [11, 0], [13, -1]
这提供了关于以下内容的运行总计的转换：
[1, 1], [2, 3], [3, 2], [7, 3], [8, 2], [10, 2], [13, 1]
2开始到3，另一个从7开始到8。这就是答案。您说每个间隔列表都是排序的且不重叠。因此，
Keep track of where you are in each list, starting at the beginning of each.
While none of the lists has run out:
If the current intervals (one from each list) all overlap:
Output the intersection of the current intervals
Find which of the current intervals has the earliest end point
Advance one position within that list.
我理解您想要做的是对区间列表应用交集操作。您可以成对进行此操作，因为交集是可结合的。
我会做类似以下的操作：
Let S be the set of sets, R = s1, s1 in S
for each set s2 in S / {s1}
for each element e1 in R
for each element e2 in s2 s.t. e1.sup < e2.inf
e1 <- intersection (e1, e2)
两个区间的交集操作是
intersection (e1,e2):
return new Interval(max(e1.inf, e2.inf), min (e1.sup, e2.sup));
[1, 1]开始，然后是[2, 1+2]，然后是[2, 1+2-1]等等（因为更改遵循1、2、-1、0、0、1、-1、-1、0、-1）。0转换无关紧要，所以我将它们删除了。 - btilly