有一种 O(n*log n)
的算法,可以从列表中删除最少数量的区间,使剩下的区间不重叠:
def maximize_nonoverlapping_count(intervals):
L = sorted(intervals, key=lambda (start, end): (end, (end - start)),
reverse=True)
iv = build_interval_tree(intervals)
result = []
while L:
result.append(L.pop())
overlapping_intervals = iv.pop(result[-1])
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]
intervals.sort(key=lambda x: (x.end, (x.end - x.start)))
tree = build_interval_tree(intervals)
result = []
for smallest in intervals:
if smallest.removed:
continue
smallest.removed = True
result.append([smallest.start, smallest.end])
tree.intersect(smallest.start, smallest.end,
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
def maximize_nonoverlapping_count(intervals):
sorted_intervals = SortedSet(intervals,
key=lambda (start, end): (end, (end - start)))
tree = SortedSet(intervals, updator=OverlappingIntervalsUpdator)
result = []
while sorted_intervals:
result.append(sorted_intervals.pop())
overlapping_intervals = tree.overlap(result[-1])
tree -= overlapping_intervals
sorted_intervals -= overlapping_intervals
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
def maximize_nonoverlapping_count(intervals):
tree = SortedSet(intervals, key=lambda (start, end): (end, (end - start)),
updator=OverlappingIntervalsUpdator)
result = []
while tree:
result.append(tree.pop())
overlapping_intervals = tree.overlap(result[-1])
tree -= overlapping_intervals
return result