Find if dates are overlapping in a list of N pairs

Question

Given list of start times and begin times, I would like to find if the list contains overlapping entries:

timesok = [('9: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')]

I borrowed some code from this very similar question to test overlapping pair of dates:

def test_overlap(dt1_st, dt1_end, dt2_st, dt2_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

My function to test the list of entries:

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

When used, it works like this:

In [257]: list(find_overlaps(timesok))
[(('9:30', '10:00'), ('10:00', '10:30')), (('9:30', '10:00'), ('10:30', '11:00')), (('10:00', '10:30'), ('10:30', '11:00'))]
Out[257]: [False, False, False]

In [258]: 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[258]: [True, False, False]

In [261]: 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[261]: [False, True, False]

However:

I am still debating myself if this is very efficient to large lists.
I was wondering if someone can offer a better solution?

Are you interested in finding all overlaps or just deciding if there is at least one overlap? — pkacprzak, Aug 26 '13 at 11:32
@pkacprzak, good point. I am interested in finding all overlaps — oz123, Aug 26 '13 at 11:33
@pkacprzak, looking into data sets with multiple overlappings, this code already shows all the overlapping pairs. — oz123, Aug 26 '13 at 11:46
I am trying to recreate this in Python 3.6.6 but am getting different results and don't know why: https://stackoverflow.com/questions/57134674/test-for-overlapping-times-in-python. Any help would be great! — JassiL, Jul 21 '19 at 16:12

score 1 · Accepted Answer · edited Aug 26 '13 at 12:03

1

I propose that way to testing the overlap, a way to find all intersections of a date :

def test_overlap(dt1_st, dt1_end, dt2_st, dt2_end):
    return not (dt1_st < dt2_end and dt1_end >dt2_st)

That's cover the all possibilities of overlapping

edited Aug 26 '13 at 12:03

oz123

27,559
27
125
187

answered Aug 26 '13 at 11:49

Philippe T.

1,182
7
11

score 0 · Answer 2 · edited May 23 '17 at 10:32

This is similar to interval overlapping problem. Elaborating on pkacprzak's post.

Sort a list of events by time. Keep another list of active elements.

Process linearly as so..

For each event/element..

add to active elements list if start point.
remove from active elements list if end point.
Additionally, at each start point, the present active elements are overlapping with the current element.

Also, look at other such solutions for interval overlaps.like this one. how to overlap intervals efficiently

score 0 · Answer 3 · answered Aug 26 '13 at 13:00

If no two pairs start at the same time, you could treat the time stamps as numeric values in "minutes since midnight", then sort the input list by the start time and then check whether the end time of any element is greater than the start time of the next element:

from operator import itemgetter
from itertools import izip

def asNumber(s):
    colon = s.find(':')
    return int(s[:colon]) * 60 + int(s[colon+1:])

def isValid(l):
  numericPairs = [(asNumber(a), asNumber(b)) for (a,b) in l]
  sortedPairs = sorted(numericPairs, key=itemgetter(0))
  return all(startB >= endA for ((startA, endA), (startB, endB)) in izip(sortedPairs, sortedPairs[1:]))

Find if dates are overlapping in a list of N pairs

3 Answers3

Linked