medium

Merge Intervals

Merge every pair of overlapping intervals into one combined interval.

1. Define the problem

Merge Intervals

Given an array of intervals where intervalsi = [starti, endi], merge all overlapping intervals and return an array of the non-overlapping intervals that cover every interval in the input. Sort the intervals by start time first — once they are sorted, any interval that overlaps the current one must come immediately after it, so a single linear scan is enough to merge them.

Constraints

  • 0 ≤ intervals.length ≤ 104
  • intervalsi.length == 2
  • 0 ≤ starti ≤ endi ≤ 105

Example

Inputintervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output[[1, 6], [8, 10], [15, 18]]

Explanation [1, 3] and [2, 6] overlap, so they merge into [1, 6].

2. Know the words first

In plain terms

Overlapping intervals
Two intervals overlap when one starts before or exactly when the other ends — for example, [1, 4] and [4, 5] overlap at 4.
3. Visualize the solution

Sort by start, then merge overlapping intervals in one pass

Sort by start, then merge overlapping intervals in one pass
Statusinit

Sorted by start. Current interval starts as [1, 3].

What happens in this step

sorted = [[1, 3], [2, 6], [8, 10], [15, 18]]  (already sorted by start)

result = [sorted[0].slice()] = [[1, 3]]

The first interval seeds result as the current "last" interval — nothing to compare against yet.
Step 1 of 5

Steps to visualize

  1. Sort the intervals by start time.
  2. Keep a "current" merged interval, starting with the first one.
  3. For each next interval, if its start is ≤ the current interval's end, they overlap — extend the current interval's end.
  4. Otherwise the current interval is finished — save it and start a new current interval.
  5. Save the last current interval once the scan ends.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Sort by start, then merge overlapping intervals in one pass
Statusinit

Sorted by start. Current interval starts as [1, 3].

What happens in this step

sorted = [[1, 3], [2, 6], [8, 10], [15, 18]]  (already sorted by start)

result = [sorted[0].slice()] = [[1, 3]]

The first interval seeds result as the current "last" interval — nothing to compare against yet.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];

  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const result = [sorted[0].slice()];

  for (let i = 1; i < sorted.length; i++) {
    const current = sorted[i];
    const last = result[result.length - 1];

    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      result.push(current.slice());
    }
  }

  return result;
}
Time
O(n log n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]][[1, 6], [8, 10], [15, 18]]example from the docstring
intervals = [[1, 2], [3, 4]][[1, 2], [3, 4]]intervals with no overlap stay separate
intervals = [[1, 10], [2, 3]][[1, 10]]one interval fully contains another
intervals = [[1, 4], [4, 5]][[1, 5]]intervals that touch exactly at an endpoint still merge
intervals = [[5, 7]][[5, 7]]smallest valid input, a single interval
intervals = [][]no intervals to merge
intervals = [[5, 7], [1, 3]][[1, 3], [5, 7]]input arrives out of start-time order
intervals = [[1, 4], [2, 5], [3, 6], [10, 12]][[1, 6], [10, 12]]a chain of overlapping intervals collapses into one

Keep reading