Merge Intervals

Medium Problem 141 of 151 Java and Python

Problem

Given an array of intervals where intervals[i] = [startᵢ, endᵢ], merge all overlapping intervals and return the non-overlapping intervals that cover exactly the same ranges.

Example 1

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

Example 2

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Why: Touching intervals count as overlapping.

Constraints

1 ≤ intervals.length ≤ 10⁴
0 ≤ startᵢ ≤ endᵢ ≤ 10⁴

Explanation

After sorting by start, any interval that overlaps the current merged block must come right after it. So scan once: if the next interval starts before (or at) the current block's end, stretch the end; otherwise start a new block.

Approach 1 · Naive

Merge pairs until nothing changes

Time O(n³) worst case
Space O(n)

Repeatedly look for any two overlapping intervals and replace them with their union, until no pair overlaps.

Loop over all pairs; if two overlap, merge them, remove one, and restart.
Stop when a full pass finds no overlap.

Java

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        for (int[] interval : intervals) {
            list.add(interval.clone());
        }
        boolean merged = true;
        while (merged) {
            merged = false;
            search:
            for (int i = 0; i < list.size(); i++) {
                for (int j = i + 1; j < list.size(); j++) {
                    int[] a = list.get(i);
                    int[] b = list.get(j);
                    if (a[0] <= b[1] && b[0] <= a[1]) {
                        a[0] = Math.min(a[0], b[0]);
                        a[1] = Math.max(a[1], b[1]);
                        list.remove(j);
                        merged = true;
                        break search;
                    }
                }
            }
        }
        list.sort((a, b) -> Integer.compare(a[0], b[0]));
        return list.toArray(new int[0][]);
    }
}

Python

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        items = [list(x) for x in intervals]
        merged = True
        while merged:
            merged = False
            for i in range(len(items)):
                for j in range(i + 1, len(items)):
                    a, b = items[i], items[j]
                    if a[0] <= b[1] and b[0] <= a[1]:
                        items[i] = [min(a[0], b[0]), max(a[1], b[1])]
                        del items[j]
                        merged = True
                        break
                if merged:
                    break
        return sorted(items)

Approach 2 · Optimal

Sort by start, then sweep

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

Sort, then keep extending the last merged interval or append a new one.

Sort intervals by start.
For each interval: if the result is empty or its last end is less than the start, append a copy.
Otherwise set the last end to max(lastEnd, end).

Java

import java.util.*;

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

Python

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        merged = []
        for start, end in sorted(intervals):
            if not merged or merged[-1][1] < start:
                merged.append([start, end])
            else:
                merged[-1][1] = max(merged[-1][1], end)
        return merged

Complexity compared

Approach	Time	Space
Naive Merge pairs until nothing changes	O(n³) worst case	O(n)
Optimal Sort by start, then sweep	O(n log n)	O(n) for the output

Key takeaways

Almost every interval problem starts with "sort by start" (or by end, for choosing which to keep).
Take max of the ends: an interval can be completely inside the previous one.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem