Python：动态区间数据结构[关闭]

我正在寻找一些 python 代码来有效计算间隔重叠。 我之前使用过 bx-python 包的间隔树，但现在需要从树中删除间隔（或者更好的是，修改它们）。 看来 bx-python 树不支持这个。

有什么指点吗？

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

Example:

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

See Python - 删除重叠列表.