Merge Intervals

mediumGreedy & Intervals27 stepsJava · Python · C++

Merge all overlapping intervals. Sort by start. Walk through them: if an interval starts before the last merged one ends, extend that end; otherwise start a new merged interval.

▶ Watch the animated trace

Traced input: intervals = [[1, 3], [8, 10], [2, 6], [15, 18], [9, 12]] → [[1, 6], [8, 12], [15, 18]]. Original problem: neetcode.io/problems/merge-intervals

Complexity

BestO(n log n)

AverageO(n log n)

WorstO(n log n)

SpaceO(n)

Sorting dominates.

Key idea

After sorting by start, overlapping intervals are next to each other.
Only the last merged interval can overlap the current one.
Touching intervals like [1,4] and [4,5] count as overlapping.

Common mistakes

Setting the new end to the current end instead of max(end, cur.end) breaks on [1,10], [2,3].
Comparing with < instead of <= misses touching intervals.

Solution

Java

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

Python

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

C++

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

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Touching Sharing an endpoint counts as overlap.	`intervals = [[1, 4], [4, 5]]`	`[[1, 5]]`
Contained max keeps the end at 10.	`intervals = [[1, 10], [2, 3]]`	`[[1, 10]]`
Single interval Nothing to merge.	`intervals = [[5, 7]]`	`[[5, 7]]`
No overlaps Kept separate.	`intervals = [[1, 2], [3, 4]]`	`[[1, 2], [3, 4]]`