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

Answer 1

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

Answer 2

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.

Answer 3

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