Merge Intervals

MediumMerge IntervalsBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an array intervals where intervals[i] = [start, end] and start <= end. Merge every group of overlapping intervals into a single interval that runs from the group's smallest start to its largest end, and return the resulting non-overlapping intervals. Intervals that only touch, such as [1,4] and [4,5], count as overlapping. The input is not necessarily in order, and the output may be in any order.

Examples

intervals = [[1,3],[2,6],[8,10],[15,18]] returns [[1,6],[8,10],[15,18]]

The highlighted pair overlaps and becomes [1,6].

[1,3] and [2,6] overlap from 2 to 3, so they merge into [1,6]. [8,10] and [15,18] don't overlap anything and stay as they are.

intervals = [[1,4],[4,5]] returns [[1,5]]

Sharing the endpoint 4 is enough to merge.

[1,4] ends exactly where [4,5] starts. Touching counts as overlapping, so they become [1,5].

intervals = [[4,7],[1,4]] returns [[1,7]]

The input is out of order. [1,4] comes first by start and touches [4,7], so together they cover 1 to 7.

Constraints

1 <= intervals.length <= 10^4
intervals[i].length == 2

Hints

Hint 1

If you could pick any order to process the intervals, which would make overlaps trivial to detect?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Sort by start. After sorting, anything that overlaps the current merged block comes right after it, so one pass is enough. For each interval, if its start is greater than the last merged end, begin a new block; otherwise extend the last block's end to the larger of the two ends. Sorting dominates the cost, and the output can hold n intervals.

Time

O(n log n)

Space

O(n)

Pitfall

When merging, keep the larger end, not the new one: [1,10] followed by [2,3] must stay [1,10]. Start a new block only when start > last end, strictly, so touching intervals like [1,4] and [4,5] still merge.

Solutions

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

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x[0])
        merged = []
        for iv in intervals:
            if not merged or merged[-1][1] < iv[0]:
                merged.append(iv)
            else:
                merged[-1][1] = max(merged[-1][1], iv[1])
        return merged