interval insertion

intervals.py

#!/usr/bin/python3

def overlaps(i1, i2):
  if i1[0] <= i2[1] and i2[0] <= i1[1]:
    return True
  return False

def insert_interval(intervals, new):

  res = []

  for i, interval in enumerate(intervals):
    if overlaps(interval, new):
      new[0] = min(interval[0], new[0])
      new[1] = max(interval[1], new[1])
    elif new[1] <= interval[0]:
         res.append(new)
         res += intervals[i:]
         return res
    else:
         res.append(interval)

  res.append(new)
  return res

# i1 before i2
assert(overlaps([0, 1], [2, 3]) == False)
# i1 after i2
assert(overlaps([2, 3], [0, 1]) == False)
# i1 overlaps end of i2
assert(overlaps([2, 4], [1, 3]) == True)
# i1 overlaps start of i2
assert(overlaps([0, 1], [1, 2]) == True)
# i1 covers i2
assert(overlaps([0, 4], [1, 2]) == True)
# i2 covers i1
assert(overlaps([1, 2], [0, 4]) == True)
# zero-sized range
assert(overlaps([0, 0], [0, 2]) == True)
# zero-sized non-overlapping range
assert(overlaps([0, 0], [1, 2]) == False)

# empty list
assert(insert_interval([ ], [4, 5]) ==
  [ [4, 5] ])
# overlapping first interval
assert(insert_interval([ [0, 3], [5, 7] ], [1, 4]) ==
  [ [0, 4], [5, 7] ])
# overlapping first interval, zero sized
assert(insert_interval([ [0, 3], [5, 7] ], [0, 0]) ==
  [ [0, 3], [5, 7] ])
# same as first interval
assert(insert_interval([ [0, 3], [5, 7] ], [0, 3]) ==
  [ [0, 3], [5, 7] ])
# entirely covers first interval
assert(insert_interval([ [0, 3], [5, 7] ], [0, 4]) ==
  [ [0, 4], [5, 7] ])

# overlapping last interval
assert(insert_interval([ [0, 3] ], [3, 5]) ==
  [ [0, 5] ])
# overlapping last interval at beginning
assert(insert_interval([ [0, 3], [5, 7] ], [4, 5]) ==
  [ [0, 3], [4, 7] ])
# before first interval
assert(insert_interval([ [2, 3], [5, 7] ], [0, 1]) ==
  [ [0, 1], [2, 3], [5, 7] ])
# in between intervals
assert(insert_interval([ [2, 3], [5, 7] ], [4, 4]) ==
  [ [2, 3], [4, 4], [5, 7] ])
assert(insert_interval([ [2, 3], [5, 7], [8, 9] ], [4, 4]) ==
  [ [2, 3], [4, 4], [5, 7], [8, 9] ])
# at end of list
assert(insert_interval([ [2, 3], [5, 7] ], [8, 9]) ==
  [ [2, 3], [5, 7], [8, 9] ])
# zero sized interval
assert(insert_interval([ [0, 3] ], [0, 0]) ==
  [ [0, 3] ])

# cover entire list
assert(insert_interval([ [0, 1], [2, 3], [3, 5] ], [0, 7]) ==
  [ [ 0, 7 ] ])