Python: 动态区间数据结构

Question

我在找一些Python代码，用来高效地计算区间重叠的情况。我之前用过bx-python这个包里的区间树，但现在需要从树中删除一些区间（或者更好的是，修改它们）。看起来bx-python的树不支持这个功能。

有没有什么建议呢？

Answer 1

如果你在找一个可以处理区间运算的Python库，可以考虑一下python-interval。顺便说一下，我是这个库的维护者。

这个库可以用来检查区间是否重叠，还能自动合并区间。例如：

>>> import intervals as I
>>> I.closed(1,2) | I.closed(2,3)
[1,3]
>>> I.closed(1,2).overlaps(I.closed(3,4))
False

如果你想专门计算重叠部分：

>>> I.closed(1,3) & I.closed(2, 4)
[2,3]

它支持开放区间和闭合区间，可以是有限的也可以是无限的。如果你想从一个区间中去掉另一个区间，只需使用差集运算符：

>>> I.closed(1, 4) - I.closed(2, 3)
[1,2) | (3,4]

如果你能提供更多具体的信息，我可以更好地帮助你。

Answer 2

也许存储所有交集区间会有所帮助。

你需要：

• 所有区间的合并边界，
• 每个交集的左边界和构成交集的区间列表。

交集区间可以存储在一个树结构中，因为它们只用左边界来表示。插入和删除区间的方法看起来是这样的（简化版）：

插入：找到新区间的左边界和右边界的交集区间，把这些交集区间分成2个或3个新的交集区间。对于每个交集区间，添加一个指针指向新插入的区间。

删除：找到左边界和右边界的交集区间，把它们合并到之前的交集区间中。对于每个交集区间，移除指向被删除区间的指针。

Answer 3

banyan 这个库可以从树结构中删除区间。举个例子，如果你有一堆区间，想要尽量少地删除一些区间，以确保剩下的区间之间没有重叠，这个操作可以在 O(n log n) 的时间内完成。你可以使用 banyan.SortedSet（一种增强版的红黑树）来实现这个功能：

from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan

def maximize_nonoverlapping_count(intervals):
    # build "interval" tree sorted by the end-point O(n log n)
    tree = SortedSet(intervals, key=lambda (start, end): (end, (end - start)),
                     updator=OverlappingIntervalsUpdator)
    result = []
    while tree: # until there are intervals left to consider
        # pop the interval with the smallest end-point, keep it in the result
        result.append(tree.pop()) # O(log n)

        # remove intervals that overlap with the popped interval
        overlapping_intervals = tree.overlap(result[-1]) # O(m log n)
        tree -= overlapping_intervals # O(m log n)
    return result

示例：

print maximize_nonoverlapping_count([[3, 4], [5, 8], [0, 6], [1, 2]])
# -> [[1, 2], [3, 4], [5, 8]]

可以参考 Python - Removing overlapping lists 了解更多信息。