Test for overlapping times in Python

Question

I am following this word for word, but am getting different results compared to the original post and I have no idea why. I am wanting to compare pairs of times to one another to check where they overlap. I am using Python 3.6.6

Find if dates are overlapping in a list of N pairs

This is what I coded:

import datetime
from collections import namedtuple
from itertools import combinations

timesok = [('09:30', '10:00'), ('10:00', '10:30'), ('10:30', '11:00')]
wrongtimes1 = [('9:30', '10:00'), ('9:00', '10:30'), ('10:30', '11:00')]
wrongtimes2=[('9:30', '10:00'), ('10:00', '10:30'), ('9:15', '9:45')]

def test_overlap(dt1_st, dt1_end, dt2_st, dt2_end):

    Range = namedtuple('Range', ['start', 'end'])

    r1 = Range(start=dt1_st, end=dt1_end)
    r2 = Range(start=dt2_st, end=dt2_end)
    latest_start = max(r1.start, r2.start)
    earliest_end = min(r1.end, r2.end)
    overlap = (earliest_end - latest_start)
    return overlap.seconds

def find_overlaps(times):
    pairs = list(combinations(times, 2))
    print(pairs)
    for pair in pairs:
        start1 = datetime.datetime.strptime(pair[0][0], '%H:%M')
        end1   = datetime.datetime.strptime(pair[0][1], '%H:%M')
        start2 = datetime.datetime.strptime(pair[1][0], '%H:%M')
        end2   = datetime.datetime.strptime(pair[1][1], '%H:%M')
        yield test_overlap(start1, end1, start2, end2) > 0

list(find_overlaps(timesok))
list(find_overlaps(wrongtimes1))
list(find_overlaps(wrongtimes2))

 # timesok result:
list(find_overlaps(timesok))
[(('09:30', '10:00'), ('10:00', '10:30')), 
 (('09:30', '10:00'), ('10:30', '11:00')), 
 (('10:00', '10:30'), ('10:30', '11:00'))]
Out[7]: [False, True, False]

 # wrongtimes1 result:
list(find_overlaps(wrongtimes1))
[(('9:30', '10:00'), ('9:00', '10:30')), 
 (('9:30', '10:00'), ('10:30', '11:00')),
 (('9:00', '10:30'), ('10:30', '11:00'))]
Out[8]: [True, True, False]

 # wrongtimes2 result:
list(find_overlaps(wrongtimes2))
[(('9:30', '10:00'), ('10:00', '10:30')), 
 (('9:30', '10:00'), ('9:15', '9:45')), 
 (('10:00', '10:30'), ('9:15', '9:45'))]
Out[9]: [False, True, True]

I think the results should be as follows (which corresponds with the original example in the link above):

Out[7]: [False, False, False]
Out[8]: [True, False, False]
Out[9]: [False, True, False]

Have I missed something very obvious here? I am a total Python newbie so be gentle with me (!)

Finomnis · Accepted Answer · 2019-07-21T18:23:32.630

overlap.seconds does not return what you think it does.

overlap is the result of a datetime subtraction, which is datetime.timedelta.

timedelta.seconds does not return the total number of seconds. It returns the second part of the delta, and if the timedelta is -1 day, 23:45:00, timedelta.seconds is 85500.

What you meant to write was overlap.total_seconds():

def test_overlap(dt1_st, dt1_end, dt2_st, dt2_end):

    Range = namedtuple('Range', ['start', 'end'])

    r1 = Range(start=dt1_st, end=dt1_end)
    r2 = Range(start=dt2_st, end=dt2_end)
    latest_start = max(r1.start, r2.start)
    earliest_end = min(r1.end, r2.end)
    overlap = (earliest_end - latest_start)
    return overlap.total_seconds()

You still have the problem that your times all have to be at the same day and cannot span wrap around midnight. I don't think using datetime is the right approach here, I think it is easier to program something custom.

Here you go:

from itertools import combinations

def test_overlap(t1_st, t1_end, t2_st, t2_end):

    def convert_to_minutes(t_str):
        hours, minutes = t_str.split(':')
        return 60*int(hours)+int(minutes)

    t1_st = convert_to_minutes(t1_st)
    t1_end = convert_to_minutes(t1_end)
    t2_st = convert_to_minutes(t2_st)
    t2_end = convert_to_minutes(t2_end)

    # Check for wrapping time differences
    if t1_end < t1_st:
        if t2_end < t2_st:
            # Both wrap, therefore they overlap at midnight
            return True
        # t2 doesn't wrap. Therefore t1 has to start after t2 and end before
        return t1_st < t2_end or t2_st < t1_end

    if t2_end < t2_st:
        # only t2 wraps. Same as before, just reversed
        return t2_st < t1_end or t1_st < t2_end

    # They don't wrap and the start of one comes after the end of the other,
    # therefore they don't overlap
    if t1_st >= t2_end or t2_st >= t1_end:
        return False

    # In all other cases, they have to overlap
    return True

times = [('09:30', '00:00'), ('07:00', '00:30'), ('10:30', '00:15'), ('12:15', '13:30'), ('10:00', '11:00'), ('00:15', '01:15')]

pairs = list(combinations(times, 2))
for pair in pairs:
    start1 = pair[0][0]
    end1   = pair[0][1]
    start2 = pair[1][0]
    end2   = pair[1][1]
    print(str(test_overlap(start1, end1, start2, end2)) + "\t" + str(pair))

True    (('09:30', '00:00'), ('07:00', '00:30'))
True    (('09:30', '00:00'), ('10:30', '00:15'))
True    (('09:30', '00:00'), ('12:15', '13:30'))
True    (('09:30', '00:00'), ('10:00', '11:00'))
False   (('09:30', '00:00'), ('00:15', '01:15'))
True    (('07:00', '00:30'), ('10:30', '00:15'))
True    (('07:00', '00:30'), ('12:15', '13:30'))
True    (('07:00', '00:30'), ('10:00', '11:00'))
True    (('07:00', '00:30'), ('00:15', '01:15'))
True    (('10:30', '00:15'), ('12:15', '13:30'))
True    (('10:30', '00:15'), ('10:00', '11:00'))
False   (('10:30', '00:15'), ('00:15', '01:15'))
False   (('12:15', '13:30'), ('10:00', '11:00'))
False   (('12:15', '13:30'), ('00:15', '01:15'))
False   (('10:00', '11:00'), ('00:15', '01:15'))

Thanks, this is really helpful. I was really tearing my hair out! In reality, my data has times like this: `times= [('09:30', '00:00'), ('07:00', '00:30'), ('10:30', '00:15'), ('12:15', '13:30', ('10:00', '11:00')]` so the first three entries span more than one day. I have noted the code above will, for example, return false for the first 2 pairs. Is there a way to overcome this. I am trying to avoid using the date in my input as I am looking at a fixed daily schedule (and date is irrelevant). — JassiL, Jul 21 '19 at 17:17
Implemented custom solution that solves the wrapping problem. Hopefully this helps. — Finomnis, Jul 21 '19 at 18:23

Test for overlapping times in Python

1 Answers1

Linked