将两组区间组合成一组区间
将两组区间组合成一组区间
提问于 2018-07-30 23:15:28
我有两组有序的间隔((表示“开始”，)表示“停止”)：
1: ( ) ( )
0---1------3------5---6---7------9---10----> time
2: ( )( ) ( )在两个列表中，它将如下所示：
intervals1 = [(0,3), (7,10)]
intervals2 = [(0,1), (1,5), (6,9)]对时间序列的进一步评估将是随着时间的推移两者的整合。为此，我希望保留间隔字符，但将其作为公共间隔。在给定的示例中，时间序列和相应的列表如下所示：
common: ( )( )( ) ( )( )( )
0---1------3------5---6---7------9---10----> time
intervals = [(0,1), (1,3), (3,5), (6,7), (7,9), (9,10)]如何有效地合并这两个时间序列？
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-07-31 01:14:42
我认为你可以使用基于堆栈的算法有效地解决这个问题，因为你知道在任何给定的位置不能有超过两个间隔重叠：
def merge_intervals(a, b):
stack = sorted(a+b, reverse=True)
while len(stack) > 1:
first = stack.pop()
second = stack.pop()
if first == second: # identical intervals can be merged
yield first
elif first[1] <= second[0]: # no overlapping, yield first interval, put back second
yield first
stack.append(second)
elif first[0] == second[0]: # overlap at start, yield shorter, put back rest of longer
if first[1] > second[1]:
first, second = second, first
yield first
stack.append((first[1], second[1]))
elif first[1] < second[1]: # partial overlap, yield first two parts, put back rest
yield first[0], second[0]
yield second[0], first[1]
stack.append((first[1], second[1]))
else: # first[1] >= second[1] # total envelopment
yield first[0], second[0]
yield second
if first[1] != second[1]:
stack.append((second[1], first[1]))
yield from stack # there may or may not be one element left over这是一个生成器，因此您将使用以下命令获得所需的输出：
intervals = list(merge_intervals(intervals1, intervals2))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51597173
复制相关文章
相似问题
腾讯云开发者
