Blind 75Medium

Merge Intervals — Sort Then Sweep

Sort intervals by start time and greedily merge overlapping ranges with a running tail pointer.

IntervalSorting

View problem on LeetCode

Problem Statement

Merge all overlapping intervals and return a list of disjoint intervals covering the same ranges.

Why This Problem Matters

Interval merging recurs in calendar, CPU scheduling, and meeting room questions.
Teaches how sorting simplifies seemingly combinatorial problems.
Serves as a base for more advanced interval DP and greedy problems.

Thought Process

Sort by starting point

Sorting ensures you only need to compare each interval with the one currently being merged.

Track current merged interval

Maintain a start/end pair; extend end while overlaps occur, otherwise finalize and reset to the new interval.

Use inclusive comparisons accurately

Overlap occurs if current.start <= tail.end. Be explicit about inclusive endpoints.

Step-by-Step Reasoning

Sort intervals ascending by start.
Initialise merged list with the first interval.
For each subsequent interval, compare with last merged: overlap → extend end; otherwise append new interval.
Return merged list.

Dry Run

[[1,3],[2,6],[8,10],[15,18]]

First two merge into [1,6]; remaining intervals remain separate.

[[1,4],[4,5]]

Inclusive boundaries mean they merge into [1,5].

Complexity Analysis

Time

O(n log n)

Space

O(n)

Why

Sorting dominates; merged list can hold up to n intervals.

Annotated Solution

JAVA

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

public class MergeIntervals {
  public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) {
      return new int[0][2];
    }

    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    List<int[]> merged = new ArrayList<>();
    int[] current = intervals[0].clone();

    for (int i = 1; i < intervals.length; i += 1) {
      int[] interval = intervals[i];
      if (interval[0] <= current[1]) {
        current[1] = Math.max(current[1], interval[1]);
      } else {
        merged.add(current);
        current = interval.clone();
      }
    }

    merged.add(current);
    return merged.toArray(new int[merged.size()][]);
  }
}

Sorting keeps comparisons local. Cloning prevents side-effects on the input array while merging intervals greedily.

Common Pitfalls

Using > instead of >= misses merges that touch at endpoints.
Mutating original interval arrays without copying may surprise callers; many solutions clone values.
Forgetting to sort leads to incorrect merges when intervals arrive out of order.

Follow-Up Questions

How would you merge in-place to reduce space?
Can you support inserting a new interval into an already merged set?

Key Takeaways

Sorting often linearises interval problems.

Carefully articulate endpoint inclusivity during interviews.

Maintain running intervals to reduce comparisons to O(1) per element.