如何求多个周期的交点

Question

Psudo代码：

timelines = [
    (range(<from>, <to>), range(<from>, <to>)),
    (range(<from>, <to>), range(<from>, <to>)),
    (range(<from>, <to>), range(<from>, <to>)),
]

<from>和<to>表示日期时间对象

此“图片”在“交集”之后显示了我需要计算的值：

^{pr2}$

如何计算这些交叉口？在

我用python编写代码，但是欢迎用任何编程语言来回答， 因为我只需要理解算法

Answer 1

步骤0:为方便起见，创建一个Range类：

from collections import namedtuple
Range = namedtuple("Range", ["start", "end"])

步骤1：创建一个计算两个范围的交集的函数。此函数适用于包含两个可比较点的任何对象：

^{pr2}$

第2步：创建一个函数，通过尝试所有可能的组合，找到两组范围的所有交点。在

def intersect_two(ranges1, ranges2):
    for range1 in ranges1:
        for range2 in ranges2:
            intersection = intersect(range1, range2)
            if intersection:
                yield intersection

步骤3:^{}使用intersect_two的范围集列表：

def intersect_all(ranges):
    return reduce(intersect_two, ranges)

为了简单起见，我使用整数，但它应该与datetime对象一样好：

>>> timelines = [
...     (Range(0, 11), Range(15, 20)),
...     (Range(8, 16), Range(19, 25)),
...     (Range(0, 10), Range(15, 22)),
... ]
>>>
>>> for intersection in intersect_all(timelines):
...     print(intersection)
...
Range(start=8, end=10)
Range(start=15, end=16)
Range(start=19, end=20)