Checking for overlap between time spans

Question

I have a list of time entries (HHMM format) with a start time and a stop. I'm having trouble figuring out how to code it in Python where it returns if there's an overlap or not in the list.

Example

Entry 1: 1030, 1245;
Entry 2: 1115, 1300
== True

Entry 1: 0900, 1030;
Entry 2: 1215, 1400
== False

Just the idea that this needs to contain a for loop if not two... — Robbie, Feb 14 '13 at 22:27
Are the entries in sorted order? (And, if not, is it reasonable to sort them first?) — abarnert, Feb 14 '13 at 22:28
Also, the first step should be to write a function that checks for overlap between two time intervals, and _then_ figure out how to write the loops or whatever that build that into a function that checks for overlaps between any intervals in a list. Do you have the first part done? — abarnert, Feb 14 '13 at 22:29
That can't be controlled but it's to be assumed they will be given chronologically in order of start times — Robbie, Feb 14 '13 at 22:31
To determine if _two_ time intervals overlap, consider that there are four time values involved: `Start1`, `End1`, `Start2`, and `End2`. Next consider all the possible relationships these could have with each other and what they would mean, such `if Start2 > End1` then the two couldn't possibly overlap. `if Start1 < Start2 and End1 > End2` then Interval2 is completely within Interval2. This sort of thing should give you an idea about how to tackle at least that part of the problem. — martineau, Feb 14 '13 at 22:42
Take a look at this link: http://stackoverflow.com/questions/4446112/search-for-interval-overlap-in-list-of-intervals — Hai Vu, Feb 15 '13 at 00:39

Roy Nieterau · Accepted Answer · 2013-02-14T23:16:48.553

First we sort the list by the start time.

Then we loop over it checking if the next start time is lower then the previous end time.

This will check if x+1 overlaps with x (not if x+2 overlaps with x, etc.)

intervals = [[100,200],[150,250],[300,400]]
intervalsSorted = sorted(intervals, key=lambda x: x[0]) # sort by start time
for x in range(1,len(intervalsSorted)):
    if intervalsSorted[x-1][1] > intervalsSorted[x][0]:
        print "{0} overlaps with {1}".format( intervals[x-1], intervals[x] )

# result: [100, 200] overlaps with [150, 250]

The following should give you all overlappings in the whole list.

intervals = [[100,200],[150,250],[300,400],[250,500]]

overlapping = [ [x,y] for x in intervals for y in intervals if x is not y and x[1]>y[0] and x[0]<y[0] ]
for x in overlapping:
    print '{0} overlaps with {1}'.format(x[0],x[1])

# results:
# [100, 200] overlaps with [150, 250]
# [250, 500] overlaps with [300, 400]

Note that this is a O(n*n) lookup. (anyone correct me here if I'm wrong!)

This is likely slower than the first (didn't test it, but I assume it is) because this iterates over the whole list for each single index. Should be similar to arbarnert's nested for loops example. But then again this does give you all the overlapping values as opposed to the first method I showed that only checked for overlapping times between those next to it (sorted by start time).

Extended test gives:

intervals = [[100,200],[150,250],[300,400],[250,500],[10,900],[1000,12300],[-151,32131],["a","c"],["b","d"],["foo","kung"]]

overlapping = [ [x,y] for x in intervals for y in intervals if x is not y and x[1]>y[0] and x[0]<y[0] ]
for x in overlapping:
    print '{0} overlaps with {1}'.format(x[0],x[1])

# results:
# [100, 200] overlaps with [150, 250]
# [250, 500] overlaps with [300, 400]
# [10, 900] overlaps with [100, 200]
# [10, 900] overlaps with [150, 250]
# [10, 900] overlaps with [300, 400]
# [10, 900] overlaps with [250, 500]
# [-151, 32131] overlaps with [100, 200]
# [-151, 32131] overlaps with [150, 250]
# [-151, 32131] overlaps with [300, 400]
# [-151, 32131] overlaps with [250, 500]
# [-151, 32131] overlaps with [10, 900]
# [-151, 32131] overlaps with [1000, 12300]
# ['a', 'c'] overlaps with ['b', 'd']

I think this is pretty close to what I need... I'm gonna run with it and see. Thanks! — Robbie, Feb 14 '13 at 23:07

score 2 · Answer 2 · answered Dec 03 '13 at 21:55

For future reference, the solution of @Roy doesn't work for intervals that have the same end or start times. The following solution does:

intervals = [[100, 200], [150, 250], [300, 400], [250, 500], [100, 150], [175, 250]]
intervals.sort()
l = len(intervals)
overlaps = []
for i in xrange(l):
  for j in xrange(i+1, l):
    x = intervals[i]
    y = intervals[j]
    if x[0] == y[0]:
      overlaps.append([x, y])
    elif x[1] == y[1]:
      overlaps.append([x, y])
    elif (x[1]>y[0] and x[0]<y[0]):
      overlaps.append([x, y])

Also, an Interval Tree could be used for these kinds of problems.

score 1 · Answer 3 · answered Aug 01 '17 at 15:04

To expand on @Roy's answer to include situations where something has the same time slot and you need to distinguish:

intervals = [[100,200, "math"],[100,200, "calc"], [150,250, "eng"],[300,400, "design"],[250,500, "lit"],[10,900, "english"],[1000,12300, "prog"],[-151,32131, "hist"]]

overlapping = [ [x,y] for x in intervals for y in intervals if x is not y and x[1]>y[0] and x[0]<y[0] or x[0]==y[0] and x[1]==y[1] and x is not y]
for x in overlapping:
    print '{0} overlaps with {1}'.format(x[0],x[1])


# Prints
#[100, 200, 'math'] overlaps with [100, 200, 'calc']
#[100, 200, 'math'] overlaps with [150, 250, 'eng']
#[100, 200, 'calc'] overlaps with [100, 200, 'math']
#[100, 200, 'calc'] overlaps with [150, 250, 'eng']
#[250, 500, 'lit'] overlaps with [300, 400, 'design']
#[10, 900, 'english'] overlaps with [100, 200, 'math']
#[10, 900, 'english'] overlaps with [100, 200, 'calc']
#[10, 900, 'english'] overlaps with [150, 250, 'eng']
#[10, 900, 'english'] overlaps with [300, 400, 'design']
#[10, 900, 'english'] overlaps with [250, 500, 'lit']
#[-151, 32131, 'hist'] overlaps with [100, 200, 'math']
#[-151, 32131, 'hist'] overlaps with [100, 200, 'calc']
#[-151, 32131, 'hist'] overlaps with [150, 250, 'eng']
#[-151, 32131, 'hist'] overlaps with [300, 400, 'design']
#[-151, 32131, 'hist'] overlaps with [250, 500, 'lit']
#[-151, 32131, 'hist'] overlaps with [10, 900, 'english']
#[-151, 32131, 'hist'] overlaps with [1000, 12300, 'prog']

score 0 · Answer 4 · answered Feb 14 '13 at 22:31

Assuming you have an intervals_overlap(interval1, interval2) function…

The first idea is a naive iteration over every pair of intervals in the list:

for interval1 in intervals:
    for interval2 in intervals:
        if interval1 is not interval2:
            if intervals_overlap(interval1, interval2):
                return True
return False

But you should be able to figure out smarter ways of dong this.

score -1 · Answer 5 · answered Nov 30 '14 at 06:33

Simple way to do it:

I change the number into string since entry 3 contains 0900, which is invalid.

entry01 = ('1030', '1245')
entry02 = ('1115', '1300')

entry03 = ('0900', '1030')
entry04 = ('1215', '1400')

def check(entry01, entry02):
    import itertools
    input_time_series = list(itertools.chain.from_iterable([entry01, entry02]))
    if input_time_series != sorted(input_time_series):
        return False
    return True

>>> check(entry01, entry02)
False
>>> check(entry03, entry04)
True

Checking for overlap between time spans

5 Answers5

Linked