Algorithm Gymnastics 23 Merge Intervals

Merge Intervals Takes an interval list as an argument and merges all duplicate intervals to create a list with only mutually exclusive intervals.

Example

Intervals: [[1,4], [2,5], [7,9]] Output: [[1,5], [7,9]] Reason: The first two intervals [1,4] and [2,5] overlap, so make them [1,5]

Intervals: [[6,7], [2,4], [5,9]] Output: [[2,4], [5,9]]

Intervals: [[1,4], [2,6], [3,5]] Output: [[1,6]]

Solution Let's look at an example of two intervals ("a" and "b") where a.start <= b.start. There are four possible scenarios:

1. a and b do not overlap.
2. A part of b overlaps with a
3. b completely overlaps a
4. a completely overlaps with b, and the two starting points are the same.

For example, it looks like this.

1. Sort the start time intervals and a.start <= b.start
2. If a overlaps b (that is, b.start <= a.end), you need to merge it into a new interval c like this:
3. Repeat the above two steps to merge c into the next interval if c overlaps with the next interval.

Implementation

class Interval:
  def __init__(self, start, end):
    self.start = start
    self.end = end

  def print_interval(self):
    print("[" + str(self.start) + ", " + str(self.end) + "]", end='')

def merge(intervals):
  if len(intervals) < 2:
    return intervals

  # sort the intervals on the start time
  intervals.sort(key=lambda x: x.start)

  mergedIntervals = []
  start = intervals[0].start
  end = intervals[0].end
  for i in range(1, len(intervals)):
    interval = intervals[i]
    if interval.start <= end:  # overlapping intervals, adjust the 'end'
      end = max(interval.end, end)
    else:  # non-overlapping interval, add the previous internval and reset
      mergedIntervals.append(Interval(start, end))
      start = interval.start
      end = interval.end

  # add the last interval
  mergedIntervals.append(Interval(start, end))
  return mergedIntervals


def main():
  print("Merged intervals: ", end='')
  for i in merge([Interval(1, 4), Interval(2, 5), Interval(7, 9)]):
    i.print_interval()
  print()

  print("Merged intervals: ", end='')
  for i in merge([Interval(6, 7), Interval(2, 4), Interval(5, 9)]):
    i.print_interval()
  print()

  print("Merged intervals: ", end='')
  for i in merge([Interval(1, 4), Interval(2, 6), Interval(3, 5)]):
    i.print_interval()
  print()


main()