Python：动态区间数据结构

Question

我正在寻找一些python代码来有效地计算间隔重叠。 我以前使用过bxpython包的间隔树，但是现在需要从树中删除间隔（或者更好的是修改它们）。 bx python树似乎不支持此功能。在

有什么建议吗？在

Answer 1

^{}支持从树中删除间隔。例如，要从间隔列表中删除最小数量的间隔，以便剩余的间隔不在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

示例：

^{pr2}$

见Python - Removing overlapping lists。在

Answer 2

如果您正在寻找一个处理区间算术的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

如果要具体计算重叠：

^{pr2}$

它支持有限或无限的开/闭区间。要删除给定间隔，只需使用差分运算符：

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

我可以帮你，如果你能更具体一点。在

Answer 3

也许存储所有交叉口的间隔时间会有所帮助。在

您需要：

• 所有区间的并集边界
• 对于每个交叉点，左边界和相交间隔列表。在

相交间隔可以存储在树中，因为它们仅用左边界表示。方法insert和delete interval如下所示（简化）：

插入：为新区间的左右边界找到相交区间，将这些相交区间拆分为2个或3个新的相交区间。对于每个交叉点之间的间隔，添加指向新间隔的指针。在

删除：找到左边界和右边界的相交间隔，并将它们合并到之前的相交间隔。对于每个交点之间的间隔，删除指向删除间隔的指针。在