Merge Intervals

You are given a list intervals where each element [start, end] describes a closed range of numbers with start <= end. The list is in no particular order.

Combine every group of ranges that overlap into a single range that covers the whole group, and return the resulting list of non-overlapping ranges sorted by their start. Two ranges overlap when they share at least one point, so ranges that merely touch, such as [2, 5] and [5, 8], must also be merged (into [2, 8]).

Example 1

Example 2

Example 3

Constraints

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Pattern Path · Intervals & Greedy · problem 111 of 169

Start simple

Repeatedly scan all pairs and merge any two that overlap until nothing changes: O(n²) per pass and up to O(n³) overall.

The key idea

Sort the ranges by their start. After sorting, every range that could overlap the current group appears right after it, so a single left-to-right pass is enough.

Keep a result list whose last entry is the group being built. For each range [s, e]:

• If s is at most the end of the last group, the two overlap (or touch), so set that end to max(lastEnd, e). The max matters: a range nested inside the group must not shrink it.
• Otherwise there is a gap. Because all later ranges start at s or later, nothing can ever reach back into the finished group, so it is safe to start a new one.

That second point is the whole correctness argument: sorting turns a global question (does anything overlap?) into a local one (does the next range overlap the last group?). The sort dominates the cost.

Complexity

• Time: O(n log n)
• Space: O(n)

Python

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda r: r[0])
        merged = []
        for start, end in intervals:
            if merged and start <= merged[-1][1]:
                # Overlaps (or touches) the current group: extend it.
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])
        return merged

JavaScript

var merge = function(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [];
  for (const [start, end] of intervals) {
    const last = merged[merged.length - 1];
    if (last && start <= last[1]) {
      // Overlaps (or touches) the current group: extend it.
      last[1] = Math.max(last[1], end);
    } else {
      merged.push([start, end]);
    }
  }
  return merged;
};

What the interviewer is checking

The interviewer wants to see you sort first to reduce a pairwise problem to a linear sweep, and handle nested and touching ranges without special cases.

Mistakes to avoid

• Setting the merged end to the new range's end instead of the maximum, which breaks on nested ranges like [1,10] and [3,4].
• Using a strict comparison (start < lastEnd) and failing to merge ranges that only touch.
• Forgetting to sort, or sorting by end instead of start.

Follow-ups to expect

• How would you insert one new range into an already merged, sorted list? (Binary search or single linear pass.)
• What if ranges arrive one at a time as a stream? (Balanced tree keyed by start.)
• How many meeting rooms do overlapping ranges need? (Sort endpoints or use a min-heap.)

In real software

Calendars combine busy blocks into free/busy summaries this way, and genome tools and log analysers merge overlapping regions or time windows before reporting them.

Practice next