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]

Screen Shot 2020-08-07 at 20.12.28.png

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. Screen Shot 2020-08-07 at 20.20.36.png

  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()

Recommended Posts

Algorithm Gymnastics 23 Merge Intervals
Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm Gymnastics 24 Reverse a Linked List
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List