Problem statement

Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return the non-overlapping intervals covering the same ranges, sorted by start.

Example 1

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

Example 2

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Touching intervals merge.

Constraints

• 1 <= intervals.length <= 20
• 0 <= start <= end <= 100

Hints for Merge Intervals

1. Hint 1

   Sort by start; overlapping intervals become adjacent.

2. Hint 2

   Extend the last merged interval while the next one starts before it ends.

How to solve Merge Intervals

Overlap is a local property once the intervals are sorted by start: anything that overlaps a given interval must begin before it ends, and after sorting such intervals sit right next to each other. So a single sweep suffices — keep extending the last merged interval while the next one starts early enough, otherwise begin a new one.

Approach

1. Sort the intervals by start.
2. Seed the output with the first interval.
3. For each subsequent interval, compare its start with the end of the last interval in the output.
4. If start <= lastEnd, they touch or overlap — extend the last interval's end to max(lastEnd, end).
5. Otherwise there is a genuine gap, so append the interval as a new block.

Why it works

After sorting, every interval that could overlap the current block starts at or before the block's end, and any interval starting later cannot overlap this block or any earlier one — the starts only increase from here. So the decision at each step is local and final, and one pass produces exactly the merged set, already sorted because the starts were.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Extend with max(lastEnd, end). A nested interval like [1,10] followed by [2,3] would otherwise shrink the block.
• Touching intervals merge here: the test is start <= lastEnd, not <.
• Sort by start, not by end — sorting by end breaks the adjacency argument.
• Compare against the last merged block's end, not the previous input interval's.

Reference solution

Python

from typing import List

def merge(intervals: List[List[int]]) -> List[List[int]]:
    s = sorted(intervals)
    out = []
    for st, en in s:
        if out and st <= out[-1][1]:
            out[-1][1] = max(out[-1][1], en)
        else:
            out.append([st, en])
    return out

Java

public static int[][] merge(int[][] intervals) {
    int[][] s = new int[intervals.length][];
    for (int i = 0; i < intervals.length; i++) s[i] = new int[]{intervals[i][0], intervals[i][1]};
    Arrays.sort(s, (a, b) -> a[0] - b[0]);
    List<int[]> out = new ArrayList<>();
    for (int[] iv : s) {
        if (!out.isEmpty() && iv[0] <= out.get(out.size() - 1)[1]) {
            if (iv[1] > out.get(out.size() - 1)[1]) out.get(out.size() - 1)[1] = iv[1];
        } else {
            out.add(new int[]{iv[0], iv[1]});
        }
    }
    return out.toArray(new int[0][]);
}

C++

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

JavaScript

var merge = function(intervals) {
    const s = intervals.slice().sort(function(a, b) { return a[0] - b[0]; });
    const out = [];
    for (const iv of s) {
        if (out.length > 0 && iv[0] <= out[out.length - 1][1]) {
            out[out.length - 1][1] = Math.max(out[out.length - 1][1], iv[1]);
        } else {
            out.push([iv[0], iv[1]]);
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium