Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Merge Intervals

Problem Statement

Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.

Example 1:

Intervals: [[1,4], [2,5], [7,9]]
Output: [[1,5], [7,9]]
Explanation: Since the first two intervals [1,4] and [2,5] overlap, we merged them into one [1,5].

Example 2:

Intervals: [[6,7], [2,4], [5,9]]
Output: [[2,4], [5,9]]
Explanation: Since the intervals [6,7] and [5,9] overlap, we merged them into one [5,9].

Example 3:

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

.....

.....

.....

Like the course? Get enrolled and start learning!
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago


#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='')

class Solution:
  def merge(self, intervals):
    result = []

    # sort the intervals in-order to merge them
    intervals.sort(key = lambda i: i.start)
    
    for interval in intervals:
      if not result: 
        result.append(interval)
      else:
        # [a, b] is the previous interval in the result array
        # [c, d] is the current internal from the loop
        a, b = result[-1].start, result[-1].end
        c, d = interval.start, interval.end
        # if overlap
        if c <= b:
          # merge then update the result array
          merged = Interval(a, max