Merge Intervals

Problem Summary

• Given a list of intervals in [start,end] format
• Merge overlapping intervals

Key Observations

• Input is not sorted
• Same start time counts as overlapping

Approach Taken

• first sort it, $O(nlogn)$ time
• if second.start < first.end then new.end = max(first.end, second.end)
• first.start will always be equal or less than second.start (because sorted by start times)
• cant store new item, unless we know next item doesn't need merging
  • example [1,3],[2,6],[3,6],[7,8]

Main Concepts Used

• Intervals

Time & Space Complexity

• Time: $O(nlogn)$ → Reason: Sorting
• Space: $O(n)$ → Reason: Output array

Code

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        merged_intervals = []
        prev = None
        for current_start, current_end in intervals:
            if not prev:
                prev = [current_start, current_end]
                continue

            prev_start, prev_end = prev
            if current_start <= prev_end:
                prev = [prev_start, max(prev_end, current_end)]
            else:
                merged_intervals.append(prev)
                prev = [current_start, current_end]
        if prev:
            merged_intervals.append(prev)
        return merged_intervals

Cleaner Code

def merge(intervals):
    # Step 1: Sort the intervals based on the starting time
    intervals.sort(key=lambda x: x[0])
    
    # Step 2: Initialize the list to store merged intervals
    merged = [intervals[0]]
    
    for i in range(1, len(intervals)):
        # previous interval in the merged list
        prev_start, prev_end = merged[-1]
        # current interval to compare with
        current_start, current_end = intervals[i]
        
        # Check if the current interval overlaps with the previous one
        if current_start <= prev_end:
            # Merge the intervals by updating the last element of merged
            merged[-1][1] = max(prev_end, current_end)
        else:
            # No overlap, add the current interval to the merged list
            merged.append(intervals[i])
    
    return merged