在时间范围列表中查找公共时间段 python

Question

我正在努力实现这种从给定的子列表列表中找到公共时隙的算法，该列表可以有多个子列表，最多 4 个，而且我的事件持续时间为例如，20 分钟，我想找到一个 20 分钟的公共时间段，满足所有存在的子列表。示例数据如下：

ranges = [
    [(datetime.datetime(2022, 6, 2, 9, 0), datetime.datetime(2022, 6, 2, 9, 30)), (datetime.datetime(2022, 6, 2, 11, 0), datetime.datetime(2022, 6, 2, 12, 10))], 
    [(datetime.datetime(2022, 6, 2, 5, 9), datetime.datetime(2022, 6, 2, 6, 56)), (datetime.datetime(2022, 6, 2, 15, 37), datetime.datetime(2022, 6, 2, 17, 24))], 
    [(datetime.datetime(2022, 6, 2, 4, 41, 3), datetime.datetime(2022, 6, 2, 6, 33, 3))], 
    [(datetime.datetime(2022, 6, 2, 20, 0), datetime.datetime(2022, 6, 2, 20, 23, 24))]
]

在每个子列表中，范围都是排序的，没有重叠，我有这个流程图，你可以使用：

我对此的看法是：

我将一个接一个地与前面的列表进行比较，并得到匹配的日期，将它们存储在一个列表中，然后在进行比较的结果上再做一次，

例如：

如果有4个子表，我要比较1、2和3、4，将两个产品的共同时间分别存储到列表a和b中，然后在列表a和b中再做一次，但是qs出现如何比较，

到目前为止我尝试过的是：

def compare_lists(list1, list2):
    gap_list = []
    for x in list1:
        for y in list2:
            if (y[0] < x[0] and y[1] < x[1]):
                if y[1] - y[0] > duration:
                    gap_list.append(y)
            if (x[0] < y[0] and x[1] < y[1]):
                if x[1] - x[0] > duration:
                    gap_list.append(x)
    return gap_list

duration = timedelta(minutes=20)

ranges = [
    [(datetime.datetime(2022, 6, 2, 9, 0), datetime.datetime(2022, 6, 2, 9, 30)), (datetime.datetime(2022, 6, 2, 11, 0), datetime.datetime(2022, 6, 2, 12, 10))], 
    [(datetime.datetime(2022, 6, 2, 5, 9), datetime.datetime(2022, 6, 2, 6, 56)), (datetime.datetime(2022, 6, 2, 15, 37), datetime.datetime(2022, 6, 2, 17, 24))], 
    [(datetime.datetime(2022, 6, 2, 4, 41, 3), datetime.datetime(2022, 6, 2, 6, 33, 3))], 
    [(datetime.datetime(2022, 6, 2, 20, 0), datetime.datetime(2022, 6, 2, 20, 23, 24))]
    ]

product_lists = []
for x, y in zip(ranges, ranges[1:]):
    product = compare_lists(x, y)
    product_lists.append(product)
print(product_lists)

不知道下一步怎么办，一团糟，打印结果是这样的

[
    [
        (datetime.datetime(2022, 6, 2, 5, 9), datetime.datetime(2022, 6, 2, 6, 56)), (datetime.datetime(2022, 6, 2, 9, 0), datetime.datetime(2022, 6, 2, 9, 30)),
        (datetime.datetime(2022, 6, 2, 5, 9), datetime.datetime(2022, 6, 2, 6, 56)), (datetime.datetime(2022, 6, 2, 11, 0), datetime.datetime(2022, 6, 2, 12, 10))
    ], 
    [
        (datetime.datetime(2022, 6, 2, 4, 41, 3), datetime.datetime(2022, 6, 2, 6, 33, 3)), 
        (datetime.datetime(2022, 6, 2, 4, 41, 3), datetime.datetime(2022, 6, 2, 6, 33, 3))
    ],
    [
        (datetime.datetime(2022, 6, 2, 4, 41, 3), datetime.datetime(2022, 6, 2, 6, 33, 3))
    ]
]

任何一点帮助将不胜感激，谢谢！

Answer 1

不知道这是否可行，因为您的样本数据没有任何有效时间，但这是我的想法

from datetime import datetime, timedelta

"""
Using two lists of time ranges, finds all ranges for which they overlap.
"""
def findCommon(list1, list2, minLength=timedelta(minutes=0)):
    newList = []
    for range1 in list1:
        for range2 in list2:
            overlapStart = max(range1[0], range2[0]) # the latest start time
            overlapEnd = min(range1[1], range2[1]) # the earliest end time
            if overlapEnd - overlapStart >= minLength:
                newList.append((overlapStart, overlapEnd))
    return newList

"""
Recursively finds the common times in several lists by taking the first two
items and finding their common ranges and then taking that new set of ranges
and applying it to the next item and so on.
"""
def reduce(listOfLists, minLength=timedelta(minutes=0)):
    if len(listOfLists) > 2:
        return reduce([findCommon(listOfLists[0], listOfLists[1], minLength)] + listOfLists[2:], minLength)
    else:
        return findCommon(listOfLists[0], listOfLists[1], minLength)

duration = timedelta(minutes=20)

ranges = [     
    [(datetime(1,1,1,1,0), datetime(1,1,1,2,0)), (datetime(1,1,1,2,30), datetime(1,1,1,3,0))],
    [(datetime(1,1,1,1,40), datetime(1,1,1,3,0))],
    [(datetime(1,1,1,1,20), datetime(1,1,1,2,50))]
] 

print(reduce(ranges, duration))

在时间范围列表中查找公共时间段 python

Find Common time slot in a list of time ranges python

python

algorithm