Editorial: Merge Intervals

1 Intuition

Sort intervals by start point. Then merge adjacent overlapping intervals. This greedy approach ensures we process intervals in order and combine overlapping ones.

2 Approach

1. Sort intervals by start position 2. Initialize result with first interval 3. For each subsequent interval: - If it overlaps with last interval in result (curr_start <= last_end) - Merge by updating last_end = max(last_end, curr_end) - Otherwise, add interval to result

3 Complexity Analysis

**Time Complexity:** O(n log n) - sorting dominates **Space Complexity:** O(1) or O(n) - depending on sorting algorithm Sorting is the bottleneck, not the merging.

4 Solution Code

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    result = [intervals[0]]
    for current in intervals[1:]:
        last = result[-1]
        if current[0] <= last[1]:
            result[-1] = [last[0], max(last[1], current[1])]
        else:
            result.append(current)
    return result

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> result;
    result.push_back(intervals[0]);
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] <= result.back()[1]) {
            result.back()[1] = max(result.back()[1], intervals[i][1]);
        } else {
            result.push_back(intervals[i]);
        }
    }
    return result;
}

5 Code Walkthrough

For [[1,3],[2,6],[8,10],[15,18]]: - Sort: [[1,3],[2,6],[8,10],[15,18]] - Result starts with [1,3] - [2,6]: 2<=3, merge → [1,6] - [8,10]: 8>6, no overlap → add [8,10] - [15,18]: 15>10, no overlap → add [15,18] Result: [[1,6],[8,10],[15,18]]