在Python中查找至少三个范围的重叠

Question

我有一个元组的列表，用来标记范围的上下限。比如说：

[(3,10), (4,11), (2,6), (8,11), (9,11)] # 5 separate ranges.

我想找出那些有三个或更多输入范围重叠的区域。例如，上面列出的元组会返回：

[(4,6), (8,11)]

我试过@WolframH在这个帖子中提供的方法

但我不知道该怎么做才能：

• 给我多个输出范围

• 设置一个至少需要三个范围重叠才能算有效输出的标准

Answer 1

当然，如果你愿意，可以通过暴力检查所有组合来解决这个问题。不过，如果你想让这个算法更高效，可以做到大约 (伪) nlogn 的复杂度。虽然理论上你可以构造一个最坏情况达到 O(n**2)，但这没什么好担心的。

基本上，你需要先对范围进行排序，然后对于给定的范围，查看它的左边，看看是否有重叠的边界。如果有重叠，再往右边查看，把重叠的区间标记为结果。下面是伪代码（其实几乎是有效的 Python 代码，看看吧）：

ranges.sort()

for left_range, current_range, right_range in sliding_window(ranges, 3):
  if left_range.right < current_range.left:
    continue
  while right_range.left < min(left_range.right, current_range.right):
      results.append(overlap(left_range, right_range))
      right_range = right_range.next
  #Before moving on to the next node, extend the current_range's right bound
  #to be the longer of (left_range.right, current_range.right)
  #This makes sense if you think about it.
  current_range.right = max(left_range.right, current_range.right)

merge_overlapping(results)

（最后你还需要合并一些可能重叠的范围，这也是一个 nlogn 的操作——不过这里的 n 通常会小很多。我不会讨论这部分代码，但它的处理方式和上面类似，都是先排序再合并。这里有个例子。）

Answer 2

你首先需要找出所有范围的组合。然后，你可以把这些组合转化为集合，并计算它们的交集：

import itertools


limits = [(3,10), (4,11), (2,6), (8,11), (9,11)]
ranges = [range(*lim) for lim in  limits]

results = []
for comb in itertools.combinations(ranges,3):
    intersection = set(comb[0]).intersection(comb[1])
    intersection = intersection.intersection(comb[2])
    if intersection and intersection not in results and\
       not any(map(intersection.issubset, results)):
        results = filter(lambda res: not intersection.issuperset(res),results)
        results.append(intersection)


result_limits =  [(res[0], res[-1]+1) for res in map(list,results)]

这样你就能得到所有三者之间的交集了。