擅长:python、mysql、java
<p><a href="https://pypi.python.org/pypi/Banyan" rel="nofollow noreferrer">^{<cd1>}</a>支持从树中删除间隔。例如,要从间隔列表中删除最小数量的间隔,以便剩余的间隔不在<code>O(n log n)</code>中重叠,可以使用<code>banyan.SortedSet</code>(增强红黑树):</p>
<pre><code>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
</code></pre>
<p>示例:</p>
^{pr2}$
<p>见<a href="https://stackoverflow.com/q/16312871/4279">Python - Removing overlapping lists</a>。在</p>