Merge Intervals Using Sorting

Problem Statement

Given a list of intervals [start, end], merge all overlapping intervals and return the non-overlapping result.

Example

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

Approach

Sort intervals by their start. Walk through them keeping the last merged interval: if the current start is <= the last end, they overlap — extend the last end to the larger of the two; otherwise append the current interval as a new block.

Complexity

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

Solution Code

Python

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

Java

int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> res = new ArrayList<>();
    for (int[] iv : intervals) {
        if (!res.isEmpty() && iv[0] <= res.get(res.size() - 1)[1])
            res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], iv[1]);
        else
            res.add(iv);
    }
    return res.toArray(new int[0][]);
}

C++

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> res;
    for (auto& iv : intervals) {
        if (!res.empty() && iv[0] <= res.back()[1])
            res.back()[1] = max(res.back()[1], iv[1]);
        else
            res.push_back(iv);
    }
    return res;
}

Key Takeaways

• Sorting by start is the key insight that makes a single merge pass possible.
• Overlap test: current start <= previous end.
• Reference: LeetCode 56 (Merge Intervals).