Merge Intervals (LC 56)

Pattern: Intervals — sort + merge
Difficulty: Medium
Key Concept: After sorting by start, each interval either extends the current merged block or starts a new one.

Problem Statement

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return a disjoint sorted list.

Input: intervals, each start_i <= end_i.
Output: merged list of intervals.

Examples:

• [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]].
• [[1,4],[4,5]] → [[1,5]].

---

1. Algorithm & Pseudocode

Brute force

1. Repeatedly find two intervals that overlap, merge them, shrink the list until no overlaps.
2. Or: for each pair, merge—O(n^3) or worse with naive scans.

Pseudocode (naive repeat):

while exists overlapping pair (a,b):
    merge a and b into one interval
return list

Optimal

1. Sort intervals by start (and by end as tiebreaker if needed).
2. Initialize cur = first interval.
3. For each next interval:
   • If interval.start <= cur.end, overlap: set cur.end = max(cur.end, interval.end).
   • Else push cur to answer, set cur = interval.
4. Push last cur.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why sort first: Without order, overlaps are non-local; sorting makes every overlap adjacent in the scan so one pass suffices.

Why max on end: Merged span ends at the farthest right endpoint seen in the overlapping chain.

Touching intervals [1,4] and [4,5]: treat start <= cur.end as merge (closed intervals).

---

3. The Dry Run

[[1,3],[2,6],[8,10],[15,18]] — already sorted by start.

step	interval	cur after	output list
init	—	[1,3]	[]
1	[2,6]	[1,6] (merge)	[]
2	[8,10]	flush [1,6], cur=[8,10]	[[1,6]]
3	[15,18]	flush [8,10], cur=[15,18]	[[1,6],[8,10]]
end	—	flush	[[1,6],[8,10],[15,18]]

---

4. Java Solution

Brute Force

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

public 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 changed = true;
        while (changed) {
            changed = false;
            outer:
            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]) {
                        int[] m = new int[] {
                            Math.min(a[0], b[0]),
                            Math.max(a[1], b[1])
                        };
                        list.remove(j);
                        list.remove(i);
                        list.add(m);
                        changed = true;
                        break outer;
                    }
                }
            }
        }

        list.sort((x, y) -> Integer.compare(x[0], y[0]));
        return list.toArray(new int[0][]);
    }
}

Time: O(n^2) rounds worst. Space: O(n).

Optimal

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

public class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][];
        }
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        int[] cur = intervals[0];

        for (int i = 1; i < intervals.length; i++) {
            int[] next = intervals[i];
            if (next[0] <= cur[1]) {
                cur[1] = Math.max(cur[1], next[1]);
            } else {
                merged.add(cur);
                cur = next;
            }
        }
        merged.add(cur);
        return merged.toArray(new int[0][]);
    }
}

Time: O(n log n) sort + O(n) scan. Space: O(n) for output list (sort may be O(log n) stack).

---

5. The “Java vs. Others” Edge

• Arrays.sort with comparator on int[][] is idiomatic; Integer.compare avoids overflow on subtraction trick.
• List<int[]> keeps pairs without a custom class; for production some teams use a small Interval record.
• Returning new int[0][] for empty input matches LeetCode style.

---

6. Complexity Summary

Approach	Time	Space	Notes
Repeated pairwise merge	O(n^2) or worse	O(n)	Not interview-grade
Sort + linear merge	O(n log n)	O(n)	Standard answer