python - 将两组间隔合并为一组间隔

Question

我有两组有序的间隔(( 表示“开始”，) 表示“停止”):

      1: (          )              (          )
         0---1------3------5---6---7------9---10----> time
      2: (   )(            )   (          )

在两个列表中，它看起来像:

intervals1 = [(0,3), (7,10)]
intervals2 = [(0,1), (1,5), (6,9)]

对时间序列的进一步评估将是两者随时间的积分。为此，我想保留间隔字符但作为公共(public)间隔。在给定的示例中，时间序列和相应的列表如下所示:

common: (   )(     )(     )   (   )(     )(  )
        0---1------3------5---6---7------9---10----> time
intervals = [(0,1), (1,3), (3,5), (6,7), (7,9), (9,10)]

如何有效地组合这两个时间序列？

Answer 1

我认为您可以使用基于堆栈的算法有效地解决这个问题，因为您知道在任何给定位置处不能重叠的间隔不超过两个:

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))