Complexity Analysis: The time complexity is dominated by building the graph, which requires comparing every interval with every other interval, resulting in O(N²) time complexity. While $N=10^4$ might theoretically pass within a generous time limit, this approach is highly inefficient and needlessly complex to implement compared to the optimal sorting approach.

Core Insight for Merge Intervals

The primary obstacle in the brute force approach is that intervals appear in random order. To determine if an interval merges with any other, we must scan the entire list.

The core insight that optimizes this process is sorting. If we sort the intervals based on their start times, we gain a powerful property: for any interval current, the only intervals that can merge with it are those that appear directly after it in the sorted list. We never need to look backward.

Once sorted, we can iterate through the list linearly. We maintain a last_merged interval. When we encounter a new interval, there are only two possibilities:

1. Overlap: The new interval starts before (or exactly when) the last_merged interval ends. Because the list is sorted by start time, we know the new interval started after the last_merged interval started. Therefore, they must overlap. We greedily extend the last_merged interval's end time.
2. No Overlap: The new interval starts strictly after the last_merged interval ends. We finalize the last_merged interval and start a new merge chain with the current interval.

Visual Description: Imagine the intervals plotted on a 1D coordinate line. Sorting aligns them from left to right based on their left-most point. As the algorithm scans from left to right, it maintains a "coverage window." If the next segment on the line begins within the current coverage window, the window extends to include the furthest point of that segment. If the next segment begins outside the window, the current window is closed (saved), and a new window begins at the start of the new segment.

Execution Flow

Consider the input: [[1,3], [8,10], [2,6], [15,18]]

1. Sort: The array becomes [[1,3], [2,6], [8,10], [15,18]].
2. Initialize: merged = [[1,3]].
3. Step 1 (Process [2,6]):
   • Last merged interval is [1,3].
   • Current interval is [2,6].
   • Check overlap: Is 2 <= 3? Yes.
   • Merge: Update the end of the last interval to max(3, 6).
   • merged is now [[1,6]].
4. Step 2 (Process [8,10]):
   • Last merged interval is [1,6].
   • Current interval is [8,10].
   • Check overlap: Is 8 <= 6? No.
   • Append: Add [8,10] to merged.
   • merged is now [[1,6], [8,10]].
5. Step 3 (Process [15,18]):
   • Last merged interval is [8,10].
   • Current interval is [15,18].
   • Check overlap: Is 15 <= 10? No.
   • Append: Add [15,18] to merged.
   • merged is now [[1,6], [8,10], [15,18]].
6. Result: Return [[1,6], [8,10], [15,18]].

Proof of Correctness

The correctness relies on the sorted order of start times. Let the sorted intervals be $I_1, I_2, ..., I_n$. If $I_i$ overlaps with $I_{i-1}$, then $start(I_i) \le end(I_{i-1})$. Since we sorted by start time, we also know $start(I_{i-1}) \le start(I_i)$. The union of these two intervals is strictly $[start(I_{i-1}), \max(end(I_{i-1}), end(I_i))]$. Because the list is sorted, no interval $I_k$ (where $k > i$) can start before $I_i$. Therefore, we can safely merge $I_i$ into the running interval without checking future intervals. If a future interval $I_k$ overlaps with the newly merged interval, it will be caught in subsequent iterations because the "active" interval has been extended. This greedy choice property ensures we never miss a merge and never merge non-overlapping intervals.

Reference Implementation

C++ Solution for LeetCode 56

cpp
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return {};
        }

        // 1. Sort intervals by start time
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> merged;
        
        // Initialize with the first interval
        merged.push_back(intervals[0]);

        // 2. Iterate through the rest
        for (int i = 1; i < intervals.size(); ++i) {
            // Reference to the last interval in the merged list
            // Using reference allows us to modify it in place
            vector<int>& last = merged.back();
            
            // Current interval boundaries
            int currentStart = intervals[i][0];
            int currentEnd = intervals[i][1];

            if (currentStart <= last[1]) {
                // Overlap: extend the end of the last interval
                last[1] = max(last[1], currentEnd);
            } else {
                // No overlap: add the new interval
                merged.push_back(intervals[i]);
            }
        }

        return merged;
    }
};

Java Solution for LeetCode 56

java
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }

        // 1. Sort intervals by start time using a lambda comparator
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();
        
        // Initialize with the first interval
        int[] currentInterval = intervals[0];
        merged.add(currentInterval);

        // 2. Iterate through the rest
        for (int[] interval : intervals) {
            int currentEnd = currentInterval[1];
            int nextStart = interval[0];
            int nextEnd = interval[1];

            if (nextStart <= currentEnd) {
                // Overlap: update the end of the current interval
                // We modify the array inside the list directly
                currentInterval[1] = Math.max(currentEnd, nextEnd);
            } else {
                // No overlap: move to the next interval
                currentInterval = interval;
                merged.add(currentInterval);
            }
        }

        // Convert List<int[]> back to int[][]
        return merged.toArray(new int[merged.size()][]);
    }
}

Python Solution for LeetCode 56

python
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []

        # 1. Sort intervals by start time
        intervals.sort(key=lambda x: x[0])

        merged = [intervals[0]]

        # 2. Iterate through the rest
        for current_start, current_end in intervals[1:]:
            last_end = merged[-1][1]

            if current_start <= last_end:
                # Overlap: update the end of the last interval
                merged[-1][1] = max(last_end, current_end)
            else:
                # No overlap: append the new interval
                merged.append([current_start, current_end])

        return merged