Python：动态区间数据结构

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python：动态区间数据结构，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1086字，纯文字阅读大概需要2分钟。

内容图文

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

内容总结

以上是互联网集市为您收集整理的Python：动态区间数据结构全部内容，希望文章能够帮你解决Python：动态区间数据结构所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端