Leetcode pattern: Merge Intervals

Main Idea

Iterate over all intervals -> If overlap, merge -> If non overlap, continue next interval

How to study

1. Read pseudocode to get overall idea on how to solve

def merge(intervals):
    # Sort intervals
    # Iterate over the input intervals     
         # Check two intervals
             # If they overlap, merge them. 
             # If they don't overlap

2. Read this AMAZING article by Tim Park. Follow along the article step by step to solve Leetcode #56. DRAW the intervals.

56. Merge Intervals

    def do_overlap(interval_1, interval_2):
        start = max(interval_1[0], interval_2[0])
        end = min(interval_1[1], interval_2[1])
        return end - start >= 0

    def merge(intervals: List[List[int]]) -> List[List[int]]:
    	# Sort intervals (based on start time)
        intervals.sort(key = lambda i: i[0])
        result = [intervals[0]]

        # Iterate over the input intervals 
        for interval in intervals[1:]:
            prevInterval = result[-1]
            # Check two intervals
            if do_overlap(prevInterval, interval):
            	# If they overlap, merge them.
                merged_start = min(interval[0], prevInterval[0])
                merged_end = max(interval[1], prevInterval[1])
                result[-1] = [merged_start, merged_end]
            else:
            	# If they don't overlap (check next interval)
                result.append(interval)
        return result

3. Try to use the pseudocode to solve a similar Leetcode #57

57. Insert Interval

    def do_overlap(interval_1, interval_2):
        start = max(interval_1[0], interval_2[0])
        end = min(interval_1[1], interval_2[1])
        return end - start >= 0

    def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        # intervals already sorted
        result = []
        
        # Iterate over the input intervals 
        for i in range(len(intervals)):
            # Check two intervals
            if do_overlap(newInterval, intervals[i]):
                # If they overlap, merge them.
                merged_start = min(intervals[i][0], newInterval[0])
                merged_end = max(intervals[i][1], newInterval[1])
                newInterval = [merged_start, merged_end]
                # we do not add newInterval to result yet 
                # because it might overlap with other following intervals
            else:
                # 2 CASES where they don't overlap
                
                # CASE 1 
                # if end value of newInterval less than
                # start value of interval
                if newInterval[1] < intervals[i][0]:
                    result.append(newInterval)
                    return result + intervals[i:]
                # CASE 2
                # if start value of newInterval larger than
                # end value of interval
                # but newInterval could overlap with other following intervals
                # so we do not append to result yet
                elif newInterval[0] > intervals[i][1]:
                    result.append(intervals[i])
        result.append(newInterval)
        return result

Problems solved using this pattern

435. Non-overlapping Intervals