Checking two time intervals are overlapping or not

Question

I have this kind of two different intervals sets:

Intervals1:
{'ending_time': '2016-02-26 07:10:40.276504', 'starting_time': '2016-02-26 07:10:39.286168'}
{'ending_time': '2016-02-26 07:10:40.722193', 'starting_time': '2016-02-26 07:10:40.301116'}
{'ending_time': '2016-02-26 07:10:41.329731', 'starting_time': '2016-02-26 07:10:40.812676'}
{'ending_time': '2016-02-26 07:10:42.146669', 'starting_time': '2016-02-26 07:10:41.419473'}
{'ending_time': '2016-02-26 07:10:42.413005', 'starting_time': '2016-02-26 07:10:42.203540'}
{'ending_time': '2016-02-26 07:10:42.686456', 'starting_time': '2016-02-26 07:10:42.442964'}
{'ending_time': '2016-02-26 07:10:43.198191', 'starting_time': '2016-02-26 07:10:42.746994'}
{'ending_time': '2016-02-26 07:10:44.502593', 'starting_time': '2016-02-26 07:10:43.288611'}
{'ending_time': '2016-02-26 07:10:46.525823', 'starting_time': '2016-02-26 07:10:44.709627'}
{'ending_time': '2016-02-26 07:10:47.098280', 'starting_time': '2016-02-26 07:10:46.886541'}
--------------------------
Interval2:
{'ending_time': '2016-02-26 07:10:41.482954', 'starting_time': '2016-02-26 07:10:39.590220'}
{'ending_time': '2016-02-26 07:10:42.615738', 'starting_time': '2016-02-26 07:10:41.649375'}
{'ending_time': '2016-02-26 07:10:46.365902', 'starting_time': '2016-02-26 07:10:45.987907'}
{'ending_time': '2016-02-26 07:10:47.698375', 'starting_time': '2016-02-26 07:10:46.510641'}

I'm converting these datetime strings to real datetime objects with this line:

datetime.datetime.strptime(dictionary['starting_time'], "%Y-%m-%d %H:%M:%S.%f")

What I'm trying to do here is to matching overlapping time intervals by comparing these two different sets.

For example; Intervals1[0] and Intervals2[0] is overlapping but Intervals1[7] and Intervals2[0] is not overlapping.

So what is the correct way to do this? A brief explanation would be enough for me.

Answer 1

datetime objects support comparisons, so you just need to check if the first start time is between the start and end of the other, or if the first end time is between the start stop of other or vice versa.

def overlap(first_inter,second_inter):
    for f,s in ((first_inter,second_inter), (second_inter,first_inter)):
        #will check both ways
        for time in (f["starting_time"], f["ending_time"]):
            if s["starting_time"] < time < s["ending_time"]:
                return True
    else:
        return False

Edit: also note that because the format of your date string has the most significant values first it would just as easily compare without making them into datetime objects.

Edit2: Here is a recipe to record all combinations and their results into a dictionary:

import itertools

combos = {(i1,i2):overlap(int1,int2)
             for (i1,int1),(i2,int2)
                in itertools.product(enumerate(Intervals1),enumerate(Intervals2))}

print(*combos.items(),sep="\n")

this way combos[0,1] will be wither Intervals[0] and Intervals[1] overlapped and so on.

Then to just get a set of overlapping times you can use:

overlapped = set(com for com,was_overlapped in combos.items() if was_overlapped)

LAST EDIT: I apologize for using really long dict comprehension, it is very difficult to work with data in confusing format, if the original list of times has a pattern to it then just using the for loop portion of the dict comprehension would yield desired result:

for (i1,int1),(i2,int2) in itertools.product(enumerate(Intervals1),enumerate(Intervals2)):
    if overlap(int1,int2):
        print(i1,i2)

or to sort the overlapped set you can use the sorted builtin:

overlapped = sorted(overlapped) #this gives a list

Answer 2

Nice and short. Took it from the colleagues, don't know the author )))

def is_overlapped(ranges):
    sorted_ranges = sorted(ranges, key=lambda begin_end: begin_end[0])
    return list(chain(*sorted_ranges)) != sorted(chain(*sorted_ranges))

##################################################################

Not overlapped:

print(is_overlapped([ (datetime(2023, 10, 1), datetime(2023, 12, 31)), (datetime(2020, 11, 1), datetime(2020, 12, 2)) ]))

False

First in second:

print(is_overlapped([ (datetime(2013, 10, 1), datetime(2013, 12, 31)), (datetime(2000, 11, 1), datetime(2020, 12, 2)) ]))

True

Second in first:

print(is_overlapped([ (datetime(2013, 10, 1), datetime(2023, 12, 31)), (datetime(2020, 11, 1), datetime(2020, 12, 2)) ]))

True

First changing into second:

print(is_overlapped([ (datetime(2010, 10, 1), datetime(2013, 12, 31)), (datetime(2013, 11, 1), datetime(2015, 12, 2)) ]))

True

Second changing into first:

print(is_overlapped([ (datetime(2011, 10, 1), datetime(2013, 12, 31)), (datetime(2010, 11, 1), datetime(2011, 12, 2)) ]))

True