python - 将两组区间合并为一组区间
问题描述
我有两组有序的间隔((
表示“开始”和)
“停止”):
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)]
如何有效地结合这两个时间序列?
解决方案
我认为您可以使用基于堆栈的算法有效地解决此问题,因为您知道在任何给定位置重叠的间隔不能超过两个:
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))
推荐阅读
- flutter - 在颤动中单击相机按钮后手电筒重新启动
- reactjs - 当 id 未知时,CRA + react-intl 崩溃
- python - 如何获取手部图像中点的坐标?
- php - 如何定义 wp-cron?
- c# - OAuth 1.0 GetAuthorizationHeader - WinForm C#
- python - music21:写入midi文件后和弦转音符?
- python - 将 Miniconda 的 Python 更新到 3.9.x,但 Miniconda 是随 Homebrew 安装的
- .net-core - 重复的“System.Reflection.AssemblyCompanyAttribute”属性 (CS0579)
- java - 在 Android Studio 中使用警报管理器设置多个警报会导致问题
- machine-learning - 准确度值在训练过程中上下波动