Merge Intervals

NeetCode: Merge Intervals · LeetCode: 56. Merge Intervals · Difficulty: Medium

Given an array of intervals [start, end], merge all overlapping intervals (touching endpoints count as overlapping) and return the resulting disjoint intervals sorted by start.

Example

Text

Input:  intervals = [[1,3],[1,5],[6,7]]    Output: [[1,5],[6,7]]
Input:  intervals = [[1,2],[2,3]]          Output: [[1,3]]

Brute force: keep merging pairs until nothing changes

Look for any two intervals that overlap; if found, replace them by their union and start over. Stop when a full pass finds no overlapping pair. Each pass checks all pairs, and there can be up to n merges. A List<int[]> is used because the number of intervals shrinks as pairs merge. ArrayList.remove(j) shifts the later elements, so one removal is O(n).

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        for (int[] iv : intervals) {
            list.add(new int[] {iv[0], iv[1]});
        }
        boolean mergedAny = true;
        while (mergedAny) {
            mergedAny = 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]) {
                        list.set(i, new int[] {Math.min(a[0], b[0]), Math.max(a[1], b[1])});
                        list.remove(j);
                        mergedAny = true;
                        break search;
                    }
                }
            }
        }
        list.sort((a, b) -> Integer.compare(a[0], b[0]));
        return list.toArray(new int[0][]);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.deepToString(solution.merge(new int[][] {{1, 3}, {1, 5}, {6, 7}})));
        System.out.println(Arrays.deepToString(solution.merge(new int[][] {{1, 2}, {2, 3}})));
        System.out.println(Arrays.deepToString(solution.merge(new int[][] {{8, 10}, {1, 3}, {2, 6}, {15, 18}})));
    }
}

Output

[[1, 5], [6, 7]]
[[1, 3]]
[[1, 6], [8, 10], [15, 18]]

The label search: names the outer loop so break search leaves both loops at once. Time: O(n^3). Space: O(n).

Optimal: sort by start, then sweep

After sorting by start, an interval can only overlap the last merged interval, never an earlier one. So walk the sorted array keeping the output as a stack: if the current interval starts at or before the last output's end, extend that end; otherwise push it as a new interval.

For [[1,3],[1,5],[6,7]] (already sorted): [1,3] starts the output, [1,5] overlaps so the end becomes 5, [6,7] starts after 5 so it is appended.

Arrays.sort with a comparator sorts the rows of an int[][] in place. The comparator uses Integer.compare rather than subtraction, which can overflow for extreme values.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.deepToString(solution.merge(new int[][] {{1, 3}, {1, 5}, {6, 7}})));
        System.out.println(Arrays.deepToString(solution.merge(new int[][] {{1, 2}, {2, 3}})));
        System.out.println(Arrays.deepToString(solution.merge(new int[][] {{8, 10}, {1, 3}, {2, 6}, {15, 18}})));
    }
}

Output

[[1, 5], [6, 7]]
[[1, 3]]
[[1, 6], [8, 10], [15, 18]]

Time: O(n log n) for the sort, O(n) for the sweep. Space: O(n).

intervals.clone() copies only the outer array, so sorting does not reorder the caller's array. The inner arrays are copied into new int[] objects before they are widened. Taking the max of the ends is required because an earlier long interval can fully contain a later short one, as with [1,10] and [2,3].