Merge Intervals

Approach Summary

Sort by start. Merge current with last result if overlapping. Two intervals overlap when start2 <= end1.

Full Solution & Approach

Sort intervals by start time so any overlap is guaranteed to be adjacent. Then walk the sorted list once, merging as you go. Keep a reference to the last interval in the result list. For each interval [start, end]: if start <= last.end, the intervals overlap or touch, so extend the last interval to max(last.end, end). Otherwise the current interval overlaps nothing already merged, so append it. The comparison uses <= so adjacent intervals like [1,2] and [2,3] merge, which matches the problem's definition of overlap. Sorting makes the one-pass merge correct: any overlap is always with the most recent interval, never with an earlier one. The sort dominates at O(n log n), then the merge itself is a single O(n) pass.

Sorting is O(n log n) and the merge pass is O(n) — total O(n log n). The output list uses O(n) space in the worst case (no overlaps).

Solution Code

Solution

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [];
  for (const [start, end] of intervals) {
    if (merged.length && start <= merged[merged.length - 1][1]) {
      merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], end);
    } else {
      merged.push([start, end]);
    }
  }
  return merged;
}

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    for (int[] interval : intervals) {
        if (!merged.isEmpty() && interval[0] <= merged.get(merged.size() - 1)[1]) {
            merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
        } else {
            merged.add(interval);
        }
    }
    return merged.toArray(new int[0][]);
}

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> merged;
    for (auto& interval : intervals) {
        if (!merged.empty() && interval[0] <= merged.back()[1]) {
            merged.back()[1] = max(merged.back()[1], interval[1]);
        } else {
            merged.push_back(interval);
        }
    }
    return merged;
}

Edge Cases to Watch

Adjacent intervals [1,2] and [2,3] — merge because the overlap check uses <=
Single interval — returned unchanged
Fully nested intervals like [1,9] and [2,5] — the max() extension handles it
Unsorted input — the sort handles it

How to Recognize This Pattern

Merge overlapping intervals
Sort by start

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(n)