python - 如何 'subtract' 在两个不同的列表中重叠元组时间范围

Question

我有两个元组列表，每个元组都由开始时间和结束时间(从纪元开始的秒数)组成，如下所示:

list1= [(2,4), (7,10), (14,22)]

list2 = [(1,3), (5,8), (9,15), (20,24)]

我需要创建一个新的元组列表(开始、结束)范围，以删除 list2 中的元组与 list1 中的元组重叠的时间间隔。

给定 list1 和 list2 时，该方法的预期输出为:

[(3,4), (8,10), (15,20)]

就其值(value)而言，list1 和 list2 都将由唯一的时间范围组成，即每个单独的列表内不会有重叠。

Answer 1

这是一个仅对列表的每个元素迭代一次的解决方案。

使用 list1 = [(2, 4), ...] 和 list2 = [(1, 3), ...]，我们有:

• 在 1 处，已删除部分的开始
• 2 点，间隔开始
• 在 3 处，已删除部分的末尾
• 4 点，间隔结束

输出由我们都在间隔内且不在已删除部分中的部分组成。

因此，我们的想法是按顺序遍历事件，跟踪我们是否处于间隔中，以及是否在已删除的部分内。

我们首先从每个列表创建一个生成器，它将生成:

• 对于第一个，Event(pos=2,toggle='in_interval')、Event(pos=4,toggle='in_interval') 等等。
• 对于第二个，Event(pos=1,toggle='in_deleted')、Event(pos=3,toggle='in_deleted')...

我们不需要关心每个值是间隔的开始还是结束，因为它只是切换状态(间隔内/外)。

然后我们可以使用heapq.merge从这两个生成器中按顺序获取事件，这将为我们提供如下内容:

事件(pos=1，toggle='in_deleted')，事件(pos=2，toggle='in_interval')，事件(pos= 3、toggle='in_deleted')、事件(pos=4,toggle='in_interval')...

每个事件都会切换关联的状态。当我们既在一个区间中又不在删除的部分中时，我们就开始了一个新的输出区间。其余的都是不言自明的......

from heapq import merge
from itertools import chain
from collections import namedtuple

def remaining(intervals, deleted):
    Event = namedtuple('Event', ['position', 'toggle'])

    int_iter = (Event(position=pos, toggle='in_interval') for pos in chain.from_iterable(intervals))
    del_iter = (Event(position=pos, toggle='in_deleted') for pos in chain.from_iterable(deleted))

    state = {'in_interval': False, 'in_deleted': False}
    start = None
    out = []

    for event in merge(int_iter, del_iter):
        state[event.toggle] = not state[event.toggle]
        if state['in_interval'] and not state['in_deleted']:
            # start a new interval
            start = event.position
        elif start is not None:
            # end an interval. If it's not empty, we append it to the output
            if event.position > start:
                out.append((start, event.position))
            start = None
    return out

示例输出:

list1 = [(2,4), (7,10), (14,22)]
list2 = [(1,3), (5,8), (9,15), (20,24)]      

print(remaining(list1, list2))
# [(3, 4), (8, 9), (15, 20)]