Problem Statement

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Additional information

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^4

Example 1:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Intervals [1, 3] and [2, 6] overlap, so they are merged into [1, 6].

Example 2:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping since they share the endpoint 4.

Sort and Merge

Intuition

The key to solving this efficiently is Sorting. If the intervals are sorted by their start time, any overlapping intervals will be adjacent to each other.

1. The Logic:

• Sort the intervals by start time.
• Create a list merged and add the first interval to it.
• Iterate through the remaining intervals. For each interval:
• Compare its start with the end of the last interval in merged.
• If they overlap (current_start <= last_end): Merge them. The new end time is the maximum of the two end times (max(last_end, current_end)).
• If they don't overlap: Simply append the current interval to merged.

Algorithm

Step 1: Sort intervals based on the start time: intervals.sort(key=lambda x: x[0]).

Step 2: Initialize merged list with the first interval: merged = [intervals[0]].

Step 3: Iterate through the rest of the intervals.

Step 4: For each interval, check if interval[0] <= merged[-1][1].

• True (Overlap): Update the end time of the last merged interval. merged[-1][1] = max(merged[-1][1], interval[1]).
• False (No Overlap): Append the current interval to merged.

Step 5: Return merged.

def merge(intervals: list[list[int]]) -> list[list[int]]:
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    
    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        
        # Check for overlap
        if start <= last_end:
            # Merge: update the end time to the max of both
            merged[-1][1] = max(last_end, end)
        else:
            # No overlap: just add it
            merged.append([start, end])
            
    return merged

Time & Space Complexity

• Time Complexity: O(N log N). Sorting takes O(N log N). The linear pass takes O(N).
• Space Complexity: O(N). In the worst case (no overlaps), we store all intervals in the merged list.