Merge Intervals

Why it belongs on this sheet

Interval questions are common in placements, and this is the base template for all of them.

Pattern

Sort by start, merge by end

Approach

Sort intervals by start time. Keep the current merged interval and either extend it if the next interval overlaps or flush it into the answer if it does not.

Java solution

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

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

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

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

Complexity

• Time: O(n log n) because of sorting
• Space: O(n) for the output list

Interview note

Say clearly why sorting by start is enough. That is the main reasoning checkpoint.