☕ DSA Java Articles

Topics › Greedy Algorithms › Medium/Hard

Merge Intervals

Medium TUF ID 712 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of closed intervals intervals[i] = [start_i, end_i] with start_i ≤ end_i, in no particular order. Merge every group of overlapping intervals into one interval and return the result sorted by start. Two closed intervals overlap when they share at least one point, so [1, 4] and [4, 5] overlap and merge into [1, 5].

Constraints: 1 ≤ n ≤ 10^4, 0 ≤ start_i ≤ end_i ≤ 10^4. The code also handles an empty array and negative endpoints.

Example 1

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

[1, 3] and [2, 6] share the points 2..3, so they become [1, 6]. The other two touch nothing.

Example 2

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

They share the single point 4, which counts as overlapping.

Approach 1: Brute force, fuse pairs until nothing overlaps

Intuition. Forget about order and apply the definition directly. Two closed intervals a and b overlap exactly when a.start ≤ b.end and b.start ≤ a.end (neither lies entirely to the left of the other). Whenever two intervals overlap, replace them by their union, [min start, max end]. Each fusion shrinks the list by one, so the process must stop, and when it stops no two intervals overlap, which is what we wanted. The final list is the same no matter which overlapping pair is fused first, because the result is just the set of connected pieces of the union of all intervals.

Algorithm.

  1. Copy the intervals into a list.
  2. Scan all pairs (i, j). At the first overlapping pair, widen list[i] to cover both, delete list[j], and restart the scan.
  3. When a full scan finds no overlap, sort by start and return.
static int[][] bruteForce(int[][] intervals) {
    List<int[]> list = new ArrayList<>();
    for (int[] iv : intervals) list.add(iv.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), b = list.get(j);
                if (a[0] <= b[1] && b[0] <= a[1]) {           // closed intervals share at least one point
                    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((x, y) -> Integer.compare(x[0], y[0]));
    return list.toArray(new int[0][]);
}

The labelled break search leaves both loops at once, because after a deletion the indices of the scan are no longer valid.

Complexity. Time O(n^3): up to n - 1 fusions, each preceded by a pair scan of up to O(n^2). Space O(n) for the working list.

Approach 2: Optimal, sort by start and sweep

Intuition. Overlap is hard to find in an unsorted pile but easy in sorted order. Sort by start and keep the merged blocks in a result list. When the next interval cur arrives, only the last block can possibly touch it:

Algorithm.

  1. Copy and sort the intervals by start.
  2. For each cur: if the result is empty or cur.start > last.end, append cur; else set last.end = max(last.end, cur.end).
  3. Return the result.
static int[][] optimal(int[][] intervals) {
    int[][] a = new int[intervals.length][];
    for (int i = 0; i < a.length; i++) a[i] = intervals[i].clone();
    Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
    List<int[]> res = new ArrayList<>();
    for (int[] cur : a) {
        int[] last = res.isEmpty() ? null : res.get(res.size() - 1);
        if (last == null || cur[0] > last[1]) {
            res.add(cur);                                     // gap: start a new block
        } else {
            last[1] = Math.max(last[1], cur[1]);              // overlap: stretch the current block
        }
    }
    return res.toArray(new int[0][]);
}

Dry run on [[5, 7], [1, 3], [2, 4], [6, 8]], sorted to [[1, 3], [2, 4], [5, 7], [6, 8]]:

cur last block action result
[1, 3] - start block [1, 3]
[2, 4] [1, 3] 2 ≤ 3, stretch to 4 [1, 4]
[5, 7] [1, 4] 5 > 4, new block [1, 4], [5, 7]
[6, 8] [5, 7] 6 ≤ 7, stretch to 8 [1, 4], [5, 8]

Complexity. Time O(n log n) for the sort; the sweep is O(n). Space O(n) for the sorted copy and the output.

Approach 3: Alternative optimal, sort starts and ends separately

Intuition. Here is a less obvious idea that is handy whenever intervals are really “events”. Pull all starts into one array and all ends into another, and sort both independently. The pairing between a start and its end is lost, yet the merged answer survives.

The reason is a counting argument. Suppose there is a gap right after the first k intervals in start order: all of them end before the next interval starts. Then the k smallest starts and the k smallest ends belong to those intervals, so ends[k-1] < starts[k]. Conversely, if ends[k-1] < starts[k], look at the intervals that own the k smallest ends. Each starts no later than it ends, so each starts before starts[k], which makes them exactly the first k intervals in start order, and they all finish before starts[k]. So a block boundary sits after position k - 1 exactly when starts[k] > ends[k-1]. A block then runs from the smallest start in the group, starts[blockStart], to the largest end in the group, ends[i].

Algorithm.

  1. Fill and sort starts and ends.
  2. For i = 0..n-1: if i is the last index or starts[i+1] > ends[i], emit [starts[blockStart], ends[i]] and set blockStart = i + 1.
static int[][] optimalSeparateSort(int[][] intervals) {
    int n = intervals.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
    }
    Arrays.sort(starts);
    Arrays.sort(ends);
    List<int[]> res = new ArrayList<>();
    int blockStart = 0;                                       // index in starts of the current block's first interval
    for (int i = 0; i < n; i++) {
        if (i == n - 1 || starts[i + 1] > ends[i]) {          // the first i+1 intervals all end before the next starts
            res.add(new int[]{starts[blockStart], ends[i]});
            blockStart = i + 1;
        }
    }
    return res.toArray(new int[0][]);
}

On example 1, starts = [1, 2, 8, 15] and ends = [3, 6, 10, 18]. At i = 0, 2 > 3 is false. At i = 1, 8 > 6 closes [1, 6]. At i = 2, 15 > 10 closes [8, 10]. The last index closes [15, 18].

Complexity. Time O(n log n) for the two sorts of primitive arrays, which are cache-friendly and avoid comparator lambdas. Space O(n).

Edge cases and pitfalls