问题：
给出了间隔列表like：
[(5, 7), (11, 116), (3, 6), (10, 12), (6, 12)] 写一个将合并重叠间隔的函数。
我的解决方案：
def merge_intervals(intervals):
"""
A simple algorithm can be used:
1. Sort the intervals in increasing order
2. Push the first interval on the stack
3. Iterate through intervals and for each one compare current interval
with the top of the stack and:
A. If current interval does not overlap, push on to stack
B. If current interval does overlap, merge both intervals in to one
and push on to stack
4. At the end return stack
"""
si = sorted(intervals, key=lambda tup: tup[0])
merged = []
for tup in si:
if not merged:
merged.append(tup)
else:
b = merged.pop()
if b[1] >= tup[0]:
new_tup = tuple([b[0], tup[1]])
merged.append(new_tup)
else:
merged.append(b)
merged.append(tup)
return merged
if __name__ == '__main__':
l = [(5, 7), (11, 116), (3, 4), (10, 12), (6, 12)]
print("Original list of ranges: {}".format(l))
merged_list = merge_intervals(l)
print("List of ranges after merge_ranges: {}".format(merged_list))
我的问题是：
运行时间：不计排序相信这在\ $ O（n）\ $中运行。用计数排序将达到\ $ O（n * \ log（n））\ $。这是正确的吗？
通常需要改进吗？
有没有更有效的方法来解决此问题？
#1 楼
此代码有一个错误。考虑merge_intervals([(0, 3), (1, 2)])。尽管应为[(0, 2)]，但返回[(0, 3)]。这可以通过new_tup = (b[0], max(b[1], tup[1]))
解决，您的代码很不错，并且实现了最简单的方法。但是，您可能需要改进变量名。
l，b或si都不具有很强的描述性，并且tup和new_tup不必要地引用其类型名称而不是其含义。相反，merged是一个非常清楚的名称。函数体的重写可能是：sorted_by_lower_bound = sorted(intervals, key=lambda tup: tup[0])
merged = []
for higher in sorted_by_lower_bound:
if not merged:
merged.append(higher)
else:
lower = merged[-1]
# test for intersection between lower and higher:
# we know via sorting that lower[0] <= higher[0]
if higher[0] <= lower[1]:
upper_bound = max(lower[1], higher[1])
merged[-1] = (lower[0], upper_bound) # replace by merged interval
else:
merged.append(higher)
return merged
请注意，我决定不使用显式的
tuple(…)构造函数–这对于从可迭代对象转换为元组非常有用。对于元组文字，可以使用(…, …)语法。我还将注释放在代码中，而不是放在文档字符串中。 Docstrings很好，但是它们旨在说明如何使用该函数（例如，期望的参数类型是什么，函数返回什么，……）。要记录实现的详细信息，请使用常规注释。
您已正确地将（平均和最坏情况）算法复杂度标识为\ $ O（n \ log n）\ $。您必须考虑排序。但是，最佳情况下的复杂度是\ $ O（n）\ $，因为Python使用的Tim Sort检测已经排序的输入。
虽然您的代码提供了一个简单而强大的解决方案，但是当然有可能降低平均算法复杂度。我希望一种自合并间隔树的平均复杂度接近\ $ O（n \ log m）\ $，其中\ $ m \ $是合并后的间隔数。
#2 楼
此问题非常适合于一种迭代方法，而不是一种生成列表的方法：如果您正在使用元数据在索引[1]之后的元组，则唯一需要更改的是必须分别设置low和high，而不是通过简单的拆包分配。评论
\ $ \ begingroup \ $
我喜欢这个为什么命名循环变量iv？它代表什么？
\ $ \ endgroup \ $
–狮子座
17年2月9日在9:02
\ $ \ begingroup \ $
另外，您可能可以执行以下操作：low，high = sorted_intervals.pop（0），这样就不必在for循环结构中分割掉第一个值。
\ $ \ endgroup \ $
–狮子座
17年2月9日在9:35
\ $ \ begingroup \ $
虽然我喜欢“生成器思想”，但我宁愿使用merged_intervals = heapq.heapify（intervals [：]）进行O（n）设置并使用heapq.heappop（merged_intervals）。
\ $ \ endgroup \ $
–灰胡子
18年4月23日在5:49
\ $ \ begingroup \ $
@greybeard的两件事：1）这意味着您正在有效地执行纯python mergesort而不是项目的优化timsort，并且不会更快。 2）heapify（）不返回列表，而是就地操作并返回None。除非您只消耗少量的固定数量的项目集，否则使用heapify（）和heappop（）并不比仅排序好。
\ $ \ endgroup \ $
–溜冰鞋
18年4月25日在4:38
\ $ \ begingroup \ $
@Mumbleskates：1）如果迭代到最后2）关于heapify（）值是正确的；注意[：]不会破坏输入。
\ $ \ endgroup \ $
–灰胡子
18年4月25日在5:09
#3 楼
此评论过于具体，无法进行评论，但很久以来就无法评论。无论如何。尽量避免使用像
for ... :
if first_iteration:
special_case_of_first_iteration
else:
normal_operations
这样的结构，这种特殊情况总是可以并且应该移出循环。从风格上讲，它节省了一个缩进级别。在性能方面，它在每次迭代时都保留了不必要的条件测试。
评论
\ $ \ begingroup \ $
如何用优雅的方式在Python中表达这一点？如xs之类的东西：special_case（xs [0]）;对于xs [1：]中的x：想到了normal_case（x），但是（不同于普通迭代）仅适用于列表，但不适用于某些可迭代项，例如生成器或集合。你会怎么写？
\ $ \ endgroup \ $
–阿蒙
2014年11月9日在2:05
\ $ \ begingroup \ $
@amon不是，我知道一个通用的食谱。它只是发生了，因此解决方案始终存在。对不起，如果我听起来很有诗意。
\ $ \ endgroup \ $
–vnp
2014年11月9日5:22
\ $ \ begingroup \ $
如何直接调用可迭代协议：if xs：special_case（next（xs））;对于xs中的x：normal_case（x）
\ $ \ endgroup \ $
– pjz
2014年11月10日4:07
\ $ \ begingroup \ $
@pjz：如图所示，它似乎处理过xs [0]两次；如果您不希望这样做，请保留迭代器：if xs：it = xs .__ iter __（）; special_case（next（it））;对于其中的x：normal_case（x）（如何减少丑陋程度？）
\ $ \ endgroup \ $
–灰胡子
16年11月24日在7:32
\ $ \ begingroup \ $
@greybeard您可以通过立即中断的迭代器上的for循环来捕获迭代器中的第一个元素，如果迭代器为空，则不会将其分配给循环变量。
\ $ \ endgroup \ $
–溜冰鞋
18年4月25日在4:59
#4 楼
您是正确的，因为排序是\ $ O（n \ log n）\ $，合并是\ $ O（n）\ $。它加起来等于\ $ O（n \ log n）\ $。通常，我不使用Python。但是我会使用更长的变量，
sortedIntervals代替si，lastInterval代替b等。我唯一要更改的是将最后一个间隔保留在变量中，而不是从变量中添加和删除它。
merged系列。#5 楼
该版本类似于@Widdershins的版本，但如果您不知道迭代方法，则更易于阅读。它根据需要通过收缩合并或复制间隔来重用排序的数组。没有元组，它变得更紧凑，因为def merge_intervals(intervals):
s = sorted(intervals, key=lambda t: t[0])
m = 0
for t in s:
if t[0] > s[m][1]:
m += 1
s[m] = t
else:
s[m] = (s[m][0], t[1])
return s[:m+1]
#6 楼
略微修改以确保加入连续的间隔。换句话说，返回[(1,10),(11,20),(30,40)]而不是返回类似[(1,20),(30,40)]的结果。注释中记录了更改。merged = []
for higher in sorted_by_lower_bound:
if not merged:
merged.append(higher)
else:
lower = merged[-1]
#added this condition branch
if higher[0] - lower[1] == 1:
merged[-1] = (lower[0], higher[1]) # replace by merged interval
#end addition. Also changed if below to elif
# test for intersection between lower and higher:
# we know via sorting that lower[0] <= higher[0]
elif higher[0] <= lower[1]:
upper_bound = max(lower[1], higher[1])
merged[-1] = (lower[0], upper_bound) # replace by merged interval
else:
merged.append(higher)
return merged
#7 楼
与上面发布的内容相比，这可能是一个更好的解决方案，我什至添加了单元测试：def compresoneadjtuple(s):
"""useful to compress adjacent entries"""
if len(s)<1:return s,True
finals=[]
for pos in range(len(s)-1):
firstt, secondt=s[pos],s[pos+1]
if (firstt[1]==secondt[0]) or (firstt[1]+1==secondt[0]):
finals.append((firstt[0],secondt[1]))
finals.extend(s[pos+2:])
return finals,False
else:
finals.append(firstt)
finals.append(s[-1])
return finals,True
def merge_intervals(intervals):
s = sorted(intervals, key=lambda t: t[0])
m = 0
for t in s:
if t[0] >= s[m][1]:
m += 1
s[m] = t
else:
s[m] = (s[m][0], t[1])
done=False
s=s[:m+1]
while(not done):
s,done=compresoneadjtuple(s)
return s
def testmergeint():
assert(merge_intervals([])==[])
assert(merge_intervals([(4,8)])==[(4, 8)])
assert(merge_intervals([(6,10)])==[(6, 10)])
assert(merge_intervals([(4,8),(6,10)])==[(4, 10)])
assert(merge_intervals([(4,8),(6,10),(11,12)])==[(4, 12)])
assert(merge_intervals([(4,8),(6,10),(11,12),(15,20)])==[(4, 12), (15, 20)])
assert(merge_intervals([(4,8),(6,10),(11,12),(15,20),(20,25)])==[(4, 12), (15, 25)])
评论
\ $ \ begingroup \ $
乍一看，您的代码看起来很丑陋。这是因为它不遵循PEP 8。
\ $ \ endgroup \ $
–罗兰·伊利格（Roland Illig）
18年4月18日在5:28
\ $ \ begingroup \ $
那很公平。我这样做是为了获得快速可行的解决方案。如果您想发布格式更好的解决方案，请相信您的功劳
\ $ \ endgroup \ $
–艾伦·施泰曼（Alan Shteyman）
18年5月9日在15:11
评论
\ $ \ begingroup \ $
您可以消除所有其他子句，并为每个子句使用相应的继续。虽然有些人不喜欢他们。
\ $ \ endgroup \ $
–狮子座
17年2月9日在8:58
\ $ \ begingroup \ $
最大值不能使这个O（n2）吗？
\ $ \ endgroup \ $
– dan-klasson
18年11月21日在18:48
\ $ \ begingroup \ $
@ dan-klasson max（）有两种形式：一种仅比较两个值，另一种则扫描整个可迭代项。在这里，使用了两个参数的形式，该形式可以在恒定时间内有效地完成操作，因此不会影响算法的复杂性。
\ $ \ endgroup \ $
–阿蒙
18年11月21日在18:51