Find Common time slot in a list of time ranges python

user_17710491 0
Viewed 75

I am struggling to implement this sort of algorithm that finds a common time slot from the given list of sub lists, that list can have more than 1 sub list, up to 4, and also I have a event duration of for say, 20 minutes, i want to find a common time slot of 20 minutes, that satisfy all the sub list present. the sample data is below:

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

In each sub list the ranges are sorted, no overlapse, i have this flow chart which you may use: problem flow chart

my take on this is:

I am gonna compare the list one after another to the proceeding one, and get the matching dates, store them in a list then do it again on the product of proceeding comparisons,

for example:

if there are 4 sub list, i'm gonna compare 1, 2 and 3, 4, store common times of both products into list a and b respectively, then do it again on list a and b, but the qs arises how to compare,

What i've tried so far is:

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)

i dont know what to do next its a mess, the print result is this

[
    [
        (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))
    ]
]

any little help would be greatly appreciated, thanks!

algorithm python
1 Answers

Idk if this works because your sample data doesn't have any valid times but this is my idea

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