Merge Overlapping Intervals

Given an array of intervals [start, end] (an int[][]), merge all overlapping intervals and return the result sorted by start. Intervals that touch, such as [1, 4] and [4, 5], overlap.

LeetCode: 56. Merge Intervals

Example

Text

Input:  [[1, 3], [2, 6], [8, 10], [15, 18]]    Output: [[1, 6], [8, 10], [15, 18]]
Input:  [[1, 4], [4, 5]]                       Output: [[1, 5]]

Two intervals a and b overlap when a.start <= b.end && b.start <= a.end.

Brute force: absorb into a disjoint result

Keep a result list of disjoint intervals. For each input interval, remove every result interval that overlaps it (through an Iterator, because removing inside a for-each loop throws ConcurrentModificationException) and grow it to cover them, then add it. Anything the grown interval overlaps must have overlapped one of the absorbed intervals, and those were disjoint from the rest, so one pass is enough.

Java

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

public class Main {
    static List<int[]> merge(int[][] intervals) {
        List<int[]> result = new ArrayList<>();
        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            Iterator<int[]> it = result.iterator();
            while (it.hasNext()) {
                int[] r = it.next();
                if (r[0] <= end && start <= r[1]) { // overlaps: absorb it
                    start = Math.min(start, r[0]);
                    end = Math.max(end, r[1]);
                    it.remove();
                }
            }
            result.add(new int[]{start, end});
        }
        result.sort((a, b) -> Integer.compare(a[0], b[0]));
        return result;
    }

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

Output

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

Time: O(n²). Space: O(n).

Optimal: sort, then extend the top

After sorting by start, intervals that overlap are next to each other. Treat the result as a stack: for each interval, if it starts at or before the end of the top interval, extend the top; otherwise push it.

interval	top before	action	result
[1, 3]		push	[1, 3]
[2, 6]	[1, 3]	2 <= 3: extend	[1, 6]
[8, 10]	[1, 6]	8 > 6: push	[1, 6], [8, 10]
[15, 18]	[8, 10]	15 > 10: push	[1, 6], [8, 10], [15, 18]

Java

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

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

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

Output

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

Time: O(n log n) for the sort; the scan is O(n). Space: O(n) for the sorted copy and the result.

Math.max(top[1], interval[1]) matters when an interval lies completely inside the top, like [2, 3] inside [1, 10]: its end is smaller and must not shrink the top.

Edge cases

Empty input: an empty result (new int[][]{} gives an empty list).
Touching intervals: merged, because the check is <=. Use < if touching intervals should stay separate.
Nested intervals: absorbed by the larger one.