☕ DSA Java Articles

Topics › Arrays › Hard

Merge Overlapping Subintervals

Medium TUF ID 715 A2ZSDE

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 a single interval and return the resulting list sorted by start. Two intervals overlap when they share at least one point, so [1, 4] and [4, 5] overlap and become [1, 5].

Constraints: 0 ≤ n ≤ 10^4, endpoints fit in a 32-bit signed integer.

Example 1

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

[1, 3] and [2, 6] overlap (they share [2, 3]) and merge into [1, 6]; the other two touch nothing.

Example 2

intervals = [[5, 7], [1, 3], [2, 4], [6, 8]]
answer = [[1, 4], [5, 8]]

After sorting, [1, 3] and [2, 4] merge, and [5, 7] and [6, 8] merge. [1, 4] and [5, 8] do not share a point.

Approach 1: Brute force

Intuition. Overlap is only easy to reason about once the intervals are sorted by start: if a starts before b, they overlap exactly when b.start ≤ a.end. So sort first. Then, for each interval that has not already been absorbed into a merged block, start a new block and scan forward, swallowing every later interval whose start is within the block’s current end and extending the end as needed. Because the list is sorted by start, the first interval that starts after the block’s end terminates the scan: everything after it starts even later.

The “already absorbed” test is simple: after merging a block that ends at E, any interval whose end is ≤ E lies entirely inside it (its start is at least the block’s start by sort order). Such intervals are skipped.

Algorithm.

  1. Sort a copy of the intervals by start (ties by end).
  2. For each index i: if the result is non-empty and a[i].end ≤ the last merged end, skip it.
  3. Otherwise set start = a[i].start, end = a[i].end, and for j > i: if a[j].start ≤ end, end = max(end, a[j].end); else stop.
  4. Append [start, end] to the result.
static int[][] bruteForce(int[][] intervals) {
    int n = intervals.length;
    int[][] a = sortedCopy(intervals);
    List<int[]> res = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (!res.isEmpty() && a[i][1] <= res.get(res.size() - 1)[1]) continue;   // already inside the last merged interval
        int start = a[i][0], end = a[i][1];
        for (int j = i + 1; j < n; j++) {
            if (a[j][0] <= end) end = Math.max(end, a[j][1]);
            else break;                                                          // sorted by start: nothing later can overlap
        }
        res.add(new int[]{start, end});
    }
    return res.toArray(new int[0][]);
}

Both approaches share a small helper that sorts a copy, so the caller’s array is not disturbed:

static int[][] sortedCopy(int[][] intervals) {
    int[][] a = new int[intervals.length][];
    for (int i = 0; i < intervals.length; i++) a[i] = intervals[i].clone();
    Arrays.sort(a, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));
    return a;
}

Complexity. Time O(n log n + n^2): sorting plus, in the worst case, a forward scan from every index. In practice the inner scan stops at the first non-overlapping interval and absorbed intervals are skipped in O(1), so the total work is usually close to linear, but the bound is still O(n^2) because the skip test and the scan can re-read the same intervals. Space O(n) for the sorted copy and result.

Approach 2: Optimal, one pass after sorting

Intuition. Once sorted, the result can be built incrementally. Keep the last merged interval at the end of the result list. The next interval either starts after that interval ends, in which case there is a gap and it begins a new block, or it starts at or before the end, in which case it overlaps and we extend the last block’s end to the larger of the two ends. Each interval is looked at exactly once; no rescanning is ever needed because the last block already summarises everything before it.

Why is comparing only with the last block enough? Blocks are produced in sorted order and are pairwise disjoint; the current interval starts at or after the last block’s start, so it cannot touch any earlier block without also touching the last one.

Algorithm.

  1. Sort a copy by start.
  2. For each interval cur:
    • If the result is empty or cur.start > last block’s end, append a copy of cur.
    • Otherwise set last block’s end to max(last.end, cur.end).
  3. Return the result.
static int[][] optimal(int[][] intervals) {
    int[][] a = sortedCopy(intervals);
    List<int[]> res = new ArrayList<>();
    for (int[] cur : a) {
        if (res.isEmpty() || cur[0] > res.get(res.size() - 1)[1]) {
            res.add(new int[]{cur[0], cur[1]});                  // gap before cur: start a new interval
        } else {
            int[] last = res.get(res.size() - 1);
            last[1] = Math.max(last[1], cur[1]);                 // overlap: extend the last interval
        }
    }
    return res.toArray(new int[0][]);
}

Dry run on [[1, 3], [2, 6], [8, 10], [15, 18]] (already sorted):

cur last block cur.start > last.end? action result
[1, 3] none   start new [[1, 3]]
[2, 6] [1, 3] 2 > 3? no extend to max(3, 6) [[1, 6]]
[8, 10] [1, 6] 8 > 6? yes start new [[1, 6], [8, 10]]
[15, 18] [8, 10] 15 > 10? yes start new [[1, 6], [8, 10], [15, 18]]

Complexity. Time O(n log n), dominated by the sort; the merge pass is O(n). Space O(n) for the sorted copy and the output (if sorting the input in place is allowed, the extra space is just the output).

The max when extending matters: [[1, 4], [2, 3]] must stay [1, 4], not shrink to [1, 3]. Taking cur.end unconditionally is a classic bug that only shows up with nested intervals.

Edge cases and pitfalls