我正在寻找一些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

例：

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

见Python – Removing overlapping lists.