Skill Set - Merge Intervals

Skills for tackling LeetCode problems - Merge Intervals.

This approach is usually used to deal with overlapping intervals. Given two intervals (‘a’ and ‘b’) there are SIX different ways the two intervals can relate to each other:

• ‘a’ and ‘b’ do not overlap. ‘a’ lies in front of ‘b’.
• ‘a’ and ‘b’ do not overlap. ‘b’ lies in front of ‘a’.
• ‘a’ completely overlaps ‘b’. (‘b’ is a subset of ‘a’)
• ‘b’ completely overlaps ‘a’. (‘a’ is a subset of ‘b’)
• ‘a’ and ‘b’ overlap. ‘b’ starts before ‘a’ ends, and ends after ‘a’ ends.
• ‘a’ and ‘b’ overlap. ‘a’ starts before ‘b’ ends, and ends after ‘b’ ends.

1. Merge Intervals

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

# Time complexity O(N Log N), where N is the number of intervals. It takes O(N) to iterate through the intervals. It takes O(N log N) to sort.
# Space complexity O(N).

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

def merge(intervals):
    if len(intervals) < 2: # nothing to merge for one interval
        return intervals
    intervals.sort(key= lambda x: x.start) # sort the intervals on the start point

    result = []
    start = intervals[0].start
    end = intervals[0].end
    for i in range(1, len(intervals)):
        interval = intervals[i]
        if interval.start <= end: # overlap
            end = max(interval.end, end)
        else: # not overlap
            result.append(Interval(start,end))
            # if it does not overlap this interval, it canont overlap next one
            # so move to the next interval
            start = interval.start 
            end = interval.end

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

Given a set of intervals, find out if any two intervals overlap.

def if_overlap(intervals): # input is a list of lists
    if len(intervals) < 2:
        return False
      
    intervals.sort(key = lambda x: x[0])
    start = intervals[0][0]
    end = intervals[0][-1]
    
    for i in range(1, len(intervals)):
        interval = intervals[i]
        if interval[0] <= end: 
            print("Intervals ["+ str(start) + ", "+ str(end) + "] and [" + str(interval[0]) + ", " + str(interval[-1]) + "] overlap.")
            return True
        else:
            start = interval[0]
            end = interval[-1]

    return False

2. Insert Interval

Given a list of non-overlapping intervals by their start time, insert a given interval at the correct position and merge all necessary intervals to produce a list that has only mutually exclusive intervals.

# Time complexity O(N), where N is the number of intervals.
# Space complexity O(N).
def insert(intervals, new_interval):
    result = []
    end_index = 0
    for i in range(len(intervals)):
        if intervals[i][-1] < new_interval[0]: # intervals before the new intervals. No overlap.
            result.append([intervals[i]])
            end_index += 1 # count number of intervals before the new one
        elif intervals[i][0] <= new_interval[-1]: # overlap, merge
            new_interval[0] = min(intervals[i][0], new_interval[0])
            new_interval[-1] = max(intervals[i][-1], new_interval[-1])
            end_index += 1 # continue count the numebr of intervals merged with the new one
        else:
            break
        
    result.append(new_interval) # append the merged new interval

    for i in range(end_index, len(intervals)):
        result.append(intervals[i]) # append the remaining intervals
    return result

3. Intervals Intersection

Given two lists of intervals, find the intersection of these two lists. Each lists consists of disjoint intervals sorted on their start time.

# Time complexity O(N+M). Space complexity O(1)
def merge(intervals_a, intervals_b):
    result = []
    i, j = 0,0
    
        # Iterate through both lists to see if any two intervals overlap
    while i < len(intervals_a) and j < len(intervals_b): 
        # a interval starts within the b interval
        case1 = intervals_a[i][0] >= intervals_b[j][0] and intervals_a[i][0] <= intervals_b[j][-1]
        # b interval starts within the a interval
        case2 = intervals_b[j][0] >= intervals_a[i][0] and intervals_b[j][0] <= intervals_a[i][-1]

        if case1 or case2:
            # find intersection
            result.append([max(intervals_a[i][0], intervals_b[j][0]), min(intervals_a[i][-1], intervals_b[j][-1])])

        # move next from the interval which is finishing first.
        if intervals_a[i][-1] < intervals_b[j][-1]:
            i += 1
        else:
            j += 1 
    
    return result

4. Conflicting Appointment

Given an array of intervals representing “N” appointments, find out if a person can attend all the appointments.

# Time complexity O(N log N). Iterating takes O(N). Sorting takes O(N log N)
# Space complexity O(N) required for sorting. Note that arrays.sort() uses Timsort which need O(N) space.
def can_attend_all_appointments(intervals):
    intervals.sort(key = lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][-1]: # overlap
            return False # conflict
    return True