获取Python中日期时间范围列表的并集和交集

Question

我有两个datetime时间范围的列表。

l1 = [(datetime.datetime(2018, 8, 29, 1, 0, 0), datetime.datetime(2018, 8, 29, 3, 0, 0)), (datetime.datetime(2018, 8, 29, 6, 0, 0), datetime.datetime(2018, 8, 29, 9, 0, 0))]
l2 = [(datetime.datetime(2018, 8, 29, 2, 0, 0), datetime.datetime(2018, 8, 29, 4, 0, 0)), (datetime.datetime(2018, 8, 29, 5, 0, 0), datetime.datetime(2018, 8, 29, 7, 0, 0))]

我想获得 l1 和 l2 的并集。

期望的输出为：

union = [(datetime.datetime(2018, 8, 29, 1, 0, 0), datetime.datetime(2018, 8, 29, 4, 0, 0)), (datetime.datetime(2018, 8, 29, 5, 0, 0), datetime.datetime(2018, 8, 29, 9, 0, 0))]
intersection = [(datetime.datetime(2018, 8, 29, 2, 0, 0), datetime.datetime(2018, 8, 29, 3, 0, 0)), (datetime.datetime(2018, 8, 29, 6, 0, 0), datetime.datetime(2018, 8, 29, 7, 0, 0))]

实际数据可能不会如此完美地对齐。

- Dawit Abate

---

你能不能让它们先设置，然后执行并集和交集操作？ - Radan

如果这些是原始值，那么这将起作用，但是在这里作者将列表项视为范围。 - Yakuza

@AChampion，列表中的元组是事件发生的时间间隔。因此，l1包含事件1发生的时间间隔，而l2则是事件2的。 - Dawit Abate

@Yakuza 不，没有任何精度。 - Dawit Abate

你需要测试所有元组彼此之间还是只需要将l1的索引0与l2的索引0进行比较？你提到实际数据不完全对齐 - 这是什么意思？ - AChampion

Answer 1

这里的回答非常有用，因为它可以压缩一个包含重叠区间的数组：

from operator import itemgetter

def consolidate(intervals):
    sorted_intervals = sorted(intervals, key=itemgetter(0))

    if not sorted_intervals:  # no intervals to merge
        return

    # low and high represent the bounds of the current run of merges
    low, high = sorted_intervals[0]

    for iv in sorted_intervals[1:]:
        if iv[0] <= high:  # new interval overlaps current run
            high = max(high, iv[1])  # merge with the current run
        else:  # current run is over
            yield low, high  # yield accumulated interval
            low, high = iv  # start new run

    yield low, high  # end the final run

合并l1和l2的结果，就是将两个列表中所有区间合并成一个：

def union(l1, l2):
    return consolidate([*l1, *l2])

l1 和 l2 的交集可以通过 AChampion 的代码充分完成（如果在 l1 中的任何范围与 l2 中的任何范围有重叠，则该重叠应包含在结果中），但这可能导致范围的分段；我们可以使用相同的函数来合并相邻或重叠的范围：

from itertools import product

def intersection(l1, l2):
    result = ((max(s1, s2), min(e1, e2)) for (s1, e1), (s2, e2) in product(l1, l2) if s1 < e2 and e1 > s2)
    return consolidate(result)

一个例子：

l1 = [(1, 7), (4, 8), (10, 15), (20, 30), (50, 60)]
l2 = [(3, 6), (8, 11), (15, 20)]
print(list(union(l1, l2)))         # [(1, 30), (50, 60)]
print(list(intersection(l1, l2)))  # [(3, 6), (10, 11)]

（为了清晰起见，示例使用整数，但它适用于任何可比较类型。具体来说，对于OP的l1和l2，该代码产生OP所需的datetime结果。）

- Amadan

Answer 2

您对日期范围的并集和交集的定义可以简单描述为：-

并集： 交集：

In []:
from itertools import product
[(min(s1, s2), max(e1, e2)) for (s1, e1), (s2, e2) in product(l1, l2) if s1 <= e2 and e1 >= s2]

Out[]:
[(datetime.datetime(2018, 8, 29, 1, 0), datetime.datetime(2018, 8, 29, 4, 0)),
 (datetime.datetime(2018, 8, 29, 5, 0), datetime.datetime(2018, 8, 29, 9, 0))]

交集：

In []:
[(max(s1, s2), min(e1, e2)) for (s1, e1), (s2, e2) in product(l1, l2) if s1 <= e2 and e1 >= s2]

Out[]:
[(datetime.datetime(2018, 8, 29, 2, 0), datetime.datetime(2018, 8, 29, 3, 0)),
 (datetime.datetime(2018, 8, 29, 6, 0), datetime.datetime(2018, 8, 29, 7, 0))]

你可以用<和>替换<=和>=，如果它们严格重叠而不仅仅是接触。

- AChampion

---

还有一件事，如果存在一个范围与任何其他范围都不重叠，则应将其包含在并集中。 - Dawit Abate

@ DawitAbate 这是一个不同的问题，可以随时提出另一个问题。希望这个回答对你有所帮助。 - AChampion

感谢您的帮助。 - Dawit Abate