Merge Intervals

How It Works

An interval is just a [start, end] pair, and most interval problems boil down to one insight: if you sort the intervals by their start value, any two intervals that overlap must be adjacent to each other in that sorted order. That means you never need to compare every pair of intervals (O(n²)); a single left-to-right sweep after sorting is enough.

The sweep keeps a "current merged interval" as you scan. For each new interval, you check whether its start is less than or equal to the end of the interval you're currently building. If it overlaps, you extend the current interval's end to the max of the two ends. If it doesn't overlap, the current interval is finished: push it to the result and start a new one with the next interval.

This same "sort, then sweep" shape solves a surprising number of variations: merging all overlapping ranges, inserting a new interval into an already-sorted list, counting the minimum number of non-overlapping intervals to remove, or figuring out the minimum number of resources (meeting rooms) needed to handle all intervals simultaneously.

When To Use It

• The input is a collection of ranges, typically represented as [start, end] pairs.
• The problem asks you to merge overlapping ranges, insert a new range, or remove the fewest ranges to eliminate overlap.
• You're modeling scheduling (meetings, bookings, reservations) where "does this overlap with that" is the core question.
• Sorting by start (sometimes end) time turns an apparently O(n²) all-pairs comparison into a single O(n log n) pass.

Time & Space Complexity

• Time: O(n log n): dominated by the initial sort; the sweep itself is O(n).
• Space: O(n) for the sorted copy and the result array (O(log n) to O(n) extra for the sort itself, depending on engine).

// Canonical merge-intervals sweep
function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];

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

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

    if (current[0] <= last[1]) {
      // Overlaps: extend the current merged interval.
      last[1] = Math.max(last[1], current[1]);
    } else {
      // No overlap: start a new merged interval.
      result.push(current);
    }
  }

  return result;
}

Alternative Approaches

• Brute-force pairwise comparison (O(n²)): check every pair of intervals for overlap; correct but far too slow once n grows, and it doesn't scale to streaming/insert variants.
• Sweep-line with event points: instead of sorting whole intervals, split each into a +1 "start" event and a -1 "end" event, sort all events by time, and sweep while tracking a running counter. This is the standard approach for "max concurrent meetings" (Meeting Rooms II) and generalizes better when you need a count over time rather than merged ranges.
• Min-heap of end times: for meeting-room-style problems, push meeting end times onto a heap as you process sorted start times, popping when a meeting has ended; the heap size at any point is the number of rooms in use.

Common Mistakes

• Forgetting to sort first: the "adjacent overlaps only" property only holds once intervals are sorted by start time; skipping the sort silently produces wrong merges.
• Using < instead of <= for the overlap check: intervals like [1,3] and [3,5] are usually considered overlapping (touching endpoints), so current[0] <= last[1] is normally correct, not strict <.
• Mutating the input array in place: sorting intervals directly (instead of a copy) can cause subtle bugs if the caller still expects the original order.
• Not handling the empty-input case: an empty list of intervals should return an empty list, not throw on sorted[0].
• Conflating "merge" and "count overlaps" logic: merging ranges and counting maximum concurrent overlaps (meeting rooms) look similar but need different sweep logic (merged-end tracking vs. an event counter or heap).

Pattern Summary

Whenever you see [start, end] pairs and a question about overlap, merging, or scheduling capacity, reach for "sort by start, then sweep once." The sort pays for itself by guaranteeing that all real overlaps happen between neighbors, turning what looks like an all-pairs problem into a clean linear scan.