Merge Intervals

The problem

An interval [start, end] covers every number from start to end, with start at most end. intervals is a list of intervals in no particular order. Numbers may be negative, and an empty list gives an empty list. Two intervals overlap when they share at least one number, so intervals that only touch at an end, such as [1, 4] and [4, 5], overlap too. Merge the intervals that overlap: every group of intervals linked by overlaps becomes one interval that covers the whole group. An interval that overlaps no other stays as it is. Return the merged intervals sorted by start. No two of them overlap.

What to write

function solve(intervals: number[][]): number[][]

Input
intervals = [[1,3],[2,6],[8,10]]

Output
[[1,6],[8,10]]

Input
intervals = [[1,4],[4,5]]

Output
[[1,5]]

Constraints

0–1,000 closed integer intervals; start ≤ end; touching endpoints overlap.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The intervals come in no particular order, and there can be 1,000 of them. Two intervals that overlap may sit far apart in the list, and one interval may overlap several others at once. The list may also be empty.

2. Hint 2: Ask a smaller question

   Take [8, 10], [1, 3], [2, 6] and merge them by hand. In which order did your eye visit the intervals? When you reach an interval, which of the earlier ones can it still overlap?

3. Hint 3: Name the pattern

   Sort the intervals by start. Then the intervals that join the one you are building come next in line, ahead of any that do not, and one pass merges them all. Sorting intervals and handling them one by one in that order is a sorted interval sweep. The signal: overlaps matter, the given order does not. Read the lesson on sorted interval sweep.

4. Hint 4: State the invariant

   After each interval, the answer is the merged form of everything visited so far: its intervals do not overlap, and they are in order of start. Only the last one can still grow, because every interval still to come starts after the ends of all the others.

5. Hint 5: Sketch the pseudocode

   Sort the intervals by start. answer = empty list. For each interval [s, e] in that order: if the answer is not empty and s is at most the end of its last interval, set that end to the larger of itself and e. Otherwise add [s, e] to the answer. Return the answer.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Sort by start. Extend the last output interval on overlap; otherwise append a new interval.

The slow way

Compare every interval with every other one, join any two that overlap, and start again until a whole round finds nothing to join. The result is right, but one round compares about n × n / 2 pairs, and there can be many rounds.

The insight

Once the intervals are sorted by start, the next interval can only join the one you are building, never an earlier one. It joins exactly when it starts at or before that interval's end. The first interval that starts after the end closes the group for good, because every later interval starts later still.

Step by step

1. Start an empty answer; only its last interval can still grow. The answer is built from left to right. Every interval in it is final except the last, which stays open because the next interval may still overlap it.
2. Visit the intervals from the smallest start to the largest. In order of start, the intervals of one merged group come one after another with no outsider between them. A copy is sorted, so the caller's list keeps its order.
3. It starts at or before the last answer interval's end: overlap. Because of the sorting it cannot start before the last answer interval does. So if it starts at or before that interval's end, the two share at least one number. Touching counts.
4. Extend that interval's end to the larger of the two ends. The merged interval must reach as far as both. The new interval may also end earlier than the last one, when the new one lies inside the last, and then the end must not move back.
5. Otherwise it opens a new interval at the end of the answer. Either the answer is still empty, or this interval starts after the last end. Every later interval starts later still, so the last answer interval is finished and a new one begins.
6. Every interval was merged or added: return the answer. Each interval went into exactly one answer interval, and new answer intervals were opened in order of start. So the answer covers the same numbers as the input, with no overlaps and in sorted order.

The same numbered steps are the comments in each solution.

function solve(intervals) {
  // 1. Start an empty answer; only its last interval can still grow
  const out = [];
  // 2. Visit the intervals from the smallest start to the largest
  for (const [a, b] of [...intervals].sort((x, y) => x[0] - y[0])) {
    // 3. It starts at or before the last answer interval's end: overlap
    const last = out[out.length - 1];
    if (last && a <= last[1]) {
      // 4. Extend that interval's end to the larger of the two ends
      last[1] = Math.max(last[1], b);
    } else {
      // 5. Otherwise it opens a new interval at the end of the answer
      out.push([a, b]);
    }
  }
  // 6. Every interval was merged or added: return the answer
  return out;
}

function solve(intervals: number[][]): number[][] {
  // 1. Start an empty answer; only its last interval can still grow
  const out = [];
  // 2. Visit the intervals from the smallest start to the largest
  for (const [a, b] of [...intervals].sort((x, y) => x[0] - y[0])) {
    // 3. It starts at or before the last answer interval's end: overlap
    const last = out[out.length - 1];
    if (last && a <= last[1]) {
      // 4. Extend that interval's end to the larger of the two ends
      last[1] = Math.max(last[1], b);
    } else {
      // 5. Otherwise it opens a new interval at the end of the answer
      out.push([a, b]);
    }
  }
  // 6. Every interval was merged or added: return the answer
  return out;
}

def solve(intervals):
    # 1. Start an empty answer; only its last interval can still grow
    merged = []
    # 2. Visit the intervals from the smallest start to the largest
    for start, end in sorted(intervals, key=lambda interval: interval[0]):
        # 3. It starts at or before the last answer interval's end: overlap
        if merged and start <= merged[-1][1]:
            # 4. Extend that interval's end to the larger of the two ends
            merged[-1][1] = max(merged[-1][1], end)
        else:
            # 5. Otherwise it opens a new interval at the end of the answer
            merged.append([start, end])
    # 6. Every interval was merged or added: return the answer
    return merged

Example 1, traced

Input
intervals = [[1,3],[2,6],[8,10]]

Output
[[1,6],[8,10]]

Why it works

The answer always equals the merged form of the intervals visited so far, and only its last interval is open. A new interval starts at or after the last one's start. So either the two overlap, and the end is extended, or the new interval starts past that end, and then nothing later can reach back either. No overlap is missed, and nothing separate is joined.

Time and space

Time O(n log n), extra space O(n). Sorting n intervals takes about n log n steps. The pass after it handles each interval once with a fixed amount of work, so sorting is the larger cost: O(n log n) time. The sorted copy and the answer each hold at most n intervals: O(n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• In JavaScript, give sort a comparison function. The plain sort() compares the intervals as text, so [10, 12] comes before [2, 3], and the two come back as the single interval [10, 12].
• Take the larger of the two ends, not the new interval's end. An interval can lie inside the one before it: [1, 10], [2, 3], [4, 5] would come back as [1, 3], [4, 5] instead of [1, 10].
• Touching counts as overlapping here, so the test is "at or before", not "before". With "before", example 2 returns [1, 4], [4, 5] instead of [1, 5].

Pattern

Sorted interval sweep. Builds on Insert Interval.

Keep going