LeetCode 56 · Medium · Intervals

Merge Intervals

Given a list of closed intervals [start, end], combine every group that overlaps or touches into one interval and return the intervals that remain.

O(n log n)time · the sort
O(n)space · output
sort by startthen one sweep

1–8 intervals · [start,end] with 0 ≤ start ≤ end ≤ 20 · any order

Number line input sorted by start · output in the bottom lane · the line marks lastEnd

public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> output = new ArrayList<>(); output.add(intervals[0]); for (int i = 1; i < intervals.length; i++) { int start = intervals[i][0]; int end = intervals[i][1]; int lastEnd = output.get(output.size() - 1)[1]; if (start <= lastEnd) { // overlaps the last output output.get(output.size() - 1)[1] = Math.max(lastEnd, end); } else { output.add(new int[]{start, end}); } } return output.toArray(new int[output.size()][]);}
[start, end]
—
lastEnd
—
output
[]

Why it works

  1. Brute force compares every pair and merges any two that overlap, repeating until nothing changes: O(n²) per pass and up to n passes.
  2. After sorting by start, overlaps are neighbours. Invariant: everything in output except the last interval is final, because every later interval starts at or after the current start and so cannot reach back past the last one.
  3. One comparison per interval: if start ≤ lastEnd it joins the last output interval, otherwise it opens a new one. The sweep is O(n); the sort makes it O(n log n). Output takes O(n) space.
  4. Pitfall: stretch with Math.max(lastEnd, end), not end. An interval inside the last one, like [2,3] in [1,10], must not shrink it. And use ≤: touching intervals such as [1,4] and [4,5] merge.
  5. Related: Insert Interval (57) skips the sort because the input is already sorted, and Non-overlapping Intervals (435) uses the same sort-and-sweep to count removals.