python - 将一组区间简化为最简单的表示

Question

我有一个定义为元组列表的“间隔”列表。我目前正在遍历整个间隔列表并比较每个间隔以检查值是否在覆盖范围内。但是，因为我的间隔列表非常大(有很多重叠)，所以这会做很多不必要的工作。

举个简单的例子:

def in_coverage(x, intervals)
    for start, end in intervals:
        if start <= x <= end:
            return True
    return False

intervals = [(1, 3), (3, 4)]
in_coverage(2, intervals) # => True
in_coverage(7, intervals) # => False

因此，为了减少此检查完成的工作量，我想预先减少间隔列表。

如何有效地将我的区间集缩减为最简单的表示形式？

例如:

[(1, 3), (3, 4)] => [(1, 4)]
[(1, 3), (3, 4), (2, 5), (7, 8), (9, 11)] => [(1, 5), (7, 8), (9, 11)]

Answer 1

您正在寻找的简单表示依赖于一个简单的观察:如果您按低值对元组进行排序，则重叠间隔是相邻的*。当然有一个警告，如果有多个重叠，那么两个重叠的间隔可以被间隔链分开，但前提是链是连接的。区间图有一些很酷的属性。

无论如何，这意味着您可以在排序列表的单次贪婪扫描中合并重叠区间。在伪代码中是这样的:

foreach 列表中的间隔 如果它与电流重叠 当前 = 组合边界是简单的凸包 min(当前低点，区间低点)，max(当前高点，区间高点) 别的 当前完成，附加到结果 当前 = 间隔

这负责最小化表示中的间隔数。如果您想最大化查找速度，那么 Ami Tavory 建议的树是可行的方法(我也猜想他的库会在树构建期间隐式处理间隔集大小的这种减少)。还有一些其他的 python 包可以做同样的事情:稀疏间隔集库。尝试在谷歌上搜索“intervalset python”并检查它是否不会将其自动更正为类似的内容。我以前用过 pyinter，它看起来很小，速度很快，界面也很简单。 Banyan 看起来更强大，但它确实可以满足您的需求 - 也许 Ami Tavory 可以将显示如何设置和查询整数区间的 3 行示例剪切并粘贴到他的答案中以清楚起见？