Merge Intervals

Problem

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

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

Solution

Approach: Sort and Merge

The key insight is to sort intervals by start time, then merge consecutive overlapping intervals.

Implementation

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # Sort by start time
        intervals.sort(key=lambda x: x[0])

        merged = []

        for interval in intervals:
            # If merged is empty or no overlap, add interval
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # Overlap - merge by extending end time
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

Approach 2: In-Place Modification

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])

        i = 0
        while i < len(intervals) - 1:
            # Check if current and next interval overlap
            if intervals[i][1] >= intervals[i + 1][0]:
                # Merge
                intervals[i][1] = max(intervals[i][1], intervals[i + 1][1])
                intervals.pop(i + 1)
            else:
                i += 1

        return intervals

Complexity Analysis

Time Complexity: O(n log n), where n is the number of intervals. Sorting dominates.
Space Complexity: O(1) or O(n) depending on sorting algorithm and whether we count output.

Key Insights

Sorting First: Sorting by start time allows us to process intervals linearly.
Overlap Check: After sorting, two consecutive intervals overlap if intervals[i][1] >= intervals[i+1][0].
Greedy Merge: Once sorted, we can greedily merge intervals from left to right.
End Time Extension: When merging, we take the maximum of the two end times (they might not be sorted by end time).
Linear Scan: After sorting, only one pass through intervals is needed.
Stack Pattern: The merged list acts like a stack - we only need to check/modify the last element.