为了从列表中删除最少数量的间隔，使得剩下的间隔不重叠，O(n*log n)算法存在：
def maximize_nonoverlapping_count(intervals):
# sort by the end-point
L = sorted(intervals, key=lambda (start, end): (end, (end - start)),
reverse=True) # O(n*logn)
iv = build_interval_tree(intervals) # O(n*log n)
result = []
while L: # until there are intervals left to consider
# pop the interval with the smallest end-point, keep it in the result
result.append(L.pop()) # O(1)
# remove intervals that overlap with the popped interval
overlapping_intervals = iv.pop(result[-1]) # O(log n + m)
remove(overlapping_intervals, from_=L)
return result
它应该产生以下结果：
f = maximize_nonoverlapping_count
assert f([[0, 133], [78, 100], [25, 30]]) == [[25, 30], [78, 100]]
assert f([[0,100],[9,10],[12,90]]) == [[9,10], [12, 90]]
assert f([[0, 100], [4, 20], [30, 35], [30, 78]]) == [[4, 20], [30, 35]]
assert f([[30, 70], [25, 40]]) == [[25, 40]]
它需要能够及时找到O(log n + m)与给定区间重叠的所有区间的数据结构，例如IntervalTree。有一些实现可以从 Python 中使用，例如quicksect.py，请参阅快速区间交集方法以了解示例用法。
这是上述算法的quicksect基于- 的实现：O(n**2)
from quicksect import IntervalNode
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
self.removed = False
def maximize_nonoverlapping_count(intervals):
intervals = [Interval(start, end) for start, end in intervals]
# sort by the end-point
intervals.sort(key=lambda x: (x.end, (x.end - x.start))) # O(n*log n)
tree = build_interval_tree(intervals) # O(n*log n)
result = []
for smallest in intervals: # O(n) (without the loop body)
# pop the interval with the smallest end-point, keep it in the result
if smallest.removed:
continue # skip removed nodes
smallest.removed = True
result.append([smallest.start, smallest.end]) # O(1)
# remove (mark) intervals that overlap with the popped interval
tree.intersect(smallest.start, smallest.end, # O(log n + m)
lambda x: setattr(x.other, 'removed', True))
return result
def build_interval_tree(intervals):
root = IntervalNode(intervals[0].start, intervals[0].end,
other=intervals[0])
return reduce(lambda tree, x: tree.insert(x.start, x.end, other=x),
intervals[1:], root)
注意：最坏情况下的时间复杂度是O(n**2)针对此实现的，因为间隔仅被标记为已删除，例如，想象这样的输入intervals，len(result) == len(intervals) / 3并且存在len(intervals) / 2跨越整个范围的间隔，然后tree.intersect()将被调用n/3次数，并且每个调用将x.other.removed = True至少执行n/2一次，即,n*n/6总共操作：
n = 6
intervals = [[0, 100], [0, 100], [0, 100], [0, 10], [10, 20], [15, 40]])
result = [[0, 10], [10, 20]]
这是一个banyan基于- 的O(n log n)实现：
from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan
def maximize_nonoverlapping_count(intervals):
# sort by the end-point O(n log n)
sorted_intervals = SortedSet(intervals,
key=lambda (start, end): (end, (end - start)))
# build "interval" tree O(n log n)
tree = SortedSet(intervals, updator=OverlappingIntervalsUpdator)
result = []
while sorted_intervals: # until there are intervals left to consider
# pop the interval with the smallest end-point, keep it in the result
result.append(sorted_intervals.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)
sorted_intervals -= overlapping_intervals # O(m log n)
return result
注意：此实现认为[0, 10]和[10, 20]间隔是重叠的：
f = maximize_nonoverlapping_count
assert f([[0, 100], [0, 10], [11, 20], [15, 40]]) == [[0, 10] ,[11, 20]]
assert f([[0, 100], [0, 10], [10, 20], [15, 40]]) == [[0, 10] ,[15, 40]]
sorted_intervals并且tree可以合并：
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