Merge Intervals

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.

You may return the answer in any order.

Note: Intervals are non-overlapping if they have no common point. For example, [1, 2] and [3, 4] are non-overlapping, but [1, 2] and [2, 3] are overlapping.

Approach

Sort intervals by start time and iterate, merging when the current interval overlaps the last merged interval. If there is no overlap, start a new interval.

Why It Works

Sorting ensures any overlaps must be adjacent in the scan. Merging overlapping intervals into a single interval preserves coverage while maintaining non-overlap among the results.

Complexity

• Time: O(n log n) due to sorting
• Space: O(n) for the output

Reference Implementation (Python)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        intervals.sort(key=lambda x: x[0])
        merged = [intervals[0]]
        for start, end in intervals[1:]:
            last_end = merged[-1][1]
            if start <= last_end:
                merged[-1][1] = max(last_end, end)
            else:
                merged.append([start, end])
        return merged