LeetCode Solutions Blog

Merge Intervals

Number: 56

Difficulty: Medium

Paid? No

Problem Description

Given an array of intervals where each interval is represented as [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Key Insights

Sort the intervals based on their start values.
Use a pointer or iteration to compare the current interval with the last merged interval.
If the current interval overlaps with the previous one, merge them by updating the end time.
Otherwise, add the current interval to the results as a new merged interval.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the intervals.
Space Complexity: O(n) to store the merged intervals.

Solution

First, sort the array of intervals based on the starting time. Then, iterate through the sorted list and check if the current interval overlaps with the last interval in the merged list. If an overlap is detected (i.e., the start of the current interval is less than or equal to the end of the last merged interval), update the last merged interval's end to be the maximum of both ends. If there is no overlap, simply add the current interval to the merged list. This approach efficiently merges overlapping intervals and ensures that all intervals are processed in a single pass after sorting.

Code Solutions

def merge(intervals):
    # Edge case: if the list is empty, return an empty list
    if not intervals:
        return []
    # Sort intervals based on the starting time
    intervals.sort(key=lambda x: x[0])
    merged = []  # List to store merged intervals
    
    # Iterate over each interval in the sorted list
    for interval in intervals:
        # If merged list is not empty and the current interval  
        # overlaps with the last one in merged, merge them
        if merged and interval[0] <= merged[-1][1]:
            # Update the end of the last interval in merged if needed
            merged[-1][1] = max(merged[-1][1], interval[1])
        else:
            # No overlap, so add the current interval to merged
            merged.append(interval)
    return merged

# Example usage:
print(merge([[1,3],[2,6],[8,10],[15,18]]))