Merge Intervals

The problem

You are given a list intervals of n intervals [start, end], in any order (n is the length of intervals). Merge every group of overlapping intervals into one, and return the intervals that are left. Two intervals overlap if they share at least one point, so [2, 5] and [5, 7] overlap.

Example 1

Input: intervals = [[8, 10], [1, 4], [3, 6], [12, 14], [9, 11]]

Output: [[1, 6], [8, 11], [12, 14]]

[1, 4] and [3, 6] become [1, 6]. [8, 10] and [9, 11] become [8, 11]. [12, 14] touches nothing.

result

Example 2

Input: intervals = [[2, 5], [5, 7]]

Output: [[2, 7]]

They share the point 5, so they merge.

Example 3

Input: intervals = [[1, 9], [3, 4]]

Output: [[1, 9]]

[3, 4] sits inside [1, 9], so it adds nothing.

Constraints

• 1 ≤ n ≤ 10,000
• 0 ≤ start ≤ end ≤ 10,000

Clarifying questions

Is the input sorted?

No. The intervals can come in any order.

Do touching intervals merge?

Yes. [2, 5] and [5, 7] share 5, so they become [2, 7].

Does the output order matter?

Any order is accepted. Sorting by start gives it for free.

Can one interval contain another?

Yes, like [3, 4] inside [1, 9]. The merged end must be the larger end, not the last one.

Spot the pattern

A list of ranges and a question about overlaps: that is the intervals pattern, and it nearly always starts with sorting by start. After sorting, any interval that overlaps the ones before it must overlap the last merged one. So one pass, comparing with just the last result, is enough.

Solutions

Merge until stableO(n³)Sort and sweepO(n log n)

Show all

This problem has two approaches. Once the list is sorted, there is no step between them.

Merge until stable O(n³)

The idea

Search the list for any two intervals that overlap. When you find a pair, replace it with one interval that covers both, and start the search again, because the new interval may now overlap others. When a full search finds no overlapping pair, you are done.

It is correct: it only stops when no two intervals overlap. But each search checks many pairs, and it may run once per merge.

Walkthrough

intervals

pairs checked

0

1. merged = True
2. while merged:
3. merged = False
4. for i in range(len(intervals)):
5. for j in range(i + 1, len(intervals)):
6. if overlap(intervals[i], intervals[j]):
7. intervals[i] = join(intervals[i], intervals[j]); del intervals[j]
8. merged = True; break
9. if merged: break
10. return intervals

Look for any two intervals that overlap. Merge them and start the search again. Stop when a full search finds nothing.

← BackStep →Play1 / 13

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Merge until stable: find any overlapping pair, merge it, search again.
    // Up to n scans of about n * n / 2 pairs, so O(n^3) time and O(1) extra memory.
    public int[][] merge(int[][] intervals) {
        java.util.List<int[]> intervalList =
            new java.util.ArrayList<>(java.util.Arrays.asList(intervals));
        boolean merged = true;
        while (merged) {
            merged = false;
            search:
            for (int i = 0; i < intervalList.size(); i++) {
                for (int j = i + 1; j < intervalList.size(); j++) {
                    int[] first = intervalList.get(i), second = intervalList.get(j);
                    // Two intervals share a point when each starts before the other ends.
                    if (first[0] <= second[1] && second[0] <= first[1]) {
                        intervalList.set(i, new int[] {
                            Math.min(first[0], second[0]), Math.max(first[1], second[1]),
                        });
                        intervalList.remove(j);
                        // The grown interval may now touch others, so search again.
                        merged = true;
                        break search;
                    }
                }
            }
        }
        return intervalList.toArray(new int[0][]);
    }
}

Big O

Time O(n³)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines check one pair and maybe merge it. They sit inside three loops: the while repeats the search, and the two for loops walk the pairs. One overlap check is 1 step.

   1. merged = True
   2. while merged:
   3. merged = False
   4. for i in range(len(intervals)):
   5. for j in range(i + 1, len(intervals)):
   6. if overlap(intervals[i], intervals[j]):
   7. intervals[i] = join(intervals[i], intervals[j]); del intervals[j]
   8. merged = True; break
   9. if merged: break
   10. return intervals

2. 2 Count the runs on Example 1

   Example 1 has 5 intervals. Scan 1 checks 4 pairs and merges. Scan 2, on 4 intervals, checks 4 pairs and merges. Scan 3, on 3 intervals, checks all 3 pairs and finds nothing.

   4 + 4 + 3 = 11 checks.

   	scan 1	scan 2	scan 3
   intervals	5	4	3
   pairs checked	4	4	3

3. 3 Write the count for any n

   Each merge removes one interval, so there are at most n − 1 merges, and n scans. In the worst case a scan checks every pair before it finds one, which is about n² / 2 pairs:

   about n × n² / 2 = ½n³

   Check it with Example 1: at most 5 scans of at most 10 pairs, so 50. The real 11 is far lower because the merges were found early.

4. 4 Keep only the part that grows fastest

   Drop the ½. What is left is n³.

   So the time is O(n³).

5. S Space: count the extra memory the same way

   The code merges inside the list it was given, and keeps only merged, i and j. The space is O(1) beyond the input.

   mergedij

Sort and sweep O(n log n)

The idea

Sort the intervals by start. Put the first one in the result. Then walk the rest:

• If an interval starts no later than the last result ends, they overlap. Stretch the last result’s end to the larger of the two ends.
• Otherwise there is a gap. Start a new result with this interval.

Why it is correct: after sorting, every interval after the gap starts even later. So none of them can reach back and touch a result that is already closed.

Walkthrough

intervals

result

empty

1. intervals.sort(key=lambda interval: interval[0])
2. result = [intervals[0]]
3. for start, end in intervals[1:]:
4. if start <= result[-1][1]:
5. result[-1][1] = max(result[-1][1], end)
6. else:
7. result.append([start, end])
8. return result

The intervals are in no order, so overlapping ones can be far apart in the list.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Sort and sweep: after sorting by start, an interval can only overlap the
    // last merged one. The sort costs O(n log n), the sweep O(n).
    public int[][] merge(int[][] intervals) {
        java.util.Arrays.sort(intervals, (first, second) -> Integer.compare(first[0], second[0]));
        java.util.List<int[]> result = new java.util.ArrayList<>();
        result.add(new int[] { intervals[0][0], intervals[0][1] });
        for (int k = 1; k < intervals.length; k++) {
            int[] last = result.get(result.size() - 1);
            int start = intervals[k][0], end = intervals[k][1];
            if (start <= last[1]) {
                // max, not end: this interval may sit inside the last one.
                last[1] = Math.max(last[1], end);
            } else {
                // A gap. Later intervals start even later, so the last one is closed.
                result.add(new int[] { start, end });
            }
        }
        return result.toArray(new int[0][]);
    }
}

Big O

Time O(n log n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two parts repeat. The sort compares intervals many times. Then the loop does one comparison and one stretch or append per interval, which is 1 step per run.

   1. intervals.sort(key=lambda interval: interval[0])
   2. result = [intervals[0]]
   3. for start, end in intervals[1:]:
   4. if start <= result[-1][1]:
   5. result[-1][1] = max(result[-1][1], end)
   6. else:
   7. result.append([start, end])
   8. return result

2. 2 Count the runs on Example 1

   Example 1 has 5 intervals. Sorting 5 items takes about 5 × log₂ 5, so about 12 steps. The loop then handles the 4 intervals after the first.

   12 + 4 = about 16 steps.

   part	sort	merge loop
   steps	about 5 × log 5 ≈ 12	4

3. 3 Write the count for any n

   n log₂ n (sort) + (n − 1) (loop)

   Check it with Example 1: 5 × 2.3 + 4 ≈ 16.

4. 4 Keep only the part that grows fastest

   Keep the sort. log n keeps growing, so n log n pulls away from the loop’s n − 1. What is left is n log n.

   So the time is O(n log n).

5. S Space: count the extra memory the same way

   The result can hold up to n intervals, when nothing overlaps. Sorting also needs some memory in most languages. The space is O(n).

   result (up to n intervals)sort space

Common mistake

Setting the end to the new interval's end

When an interval sits inside the last result, like [3, 4] after [1, 9], its end is smaller. Writing result[-1][1] = end would shrink [1, 9] to [1, 4]. Take the max of the two ends.

Tested at the limits

2,000 random lists of 1 to 7 intervals with ends from 0 to 10, so touching ends, nested intervals, repeats and zero-length intervals come up often. Merge until stable and sort and sweep gave the same answer every time.

Largest inputs	Result
10,000 intervals (the most allowed), shuffled, none touching, so nothing merges. Sort and sweep.	0.004 s, and about 0.8 MB of extra memory: the result holds all 10,000 intervals, plus the sort.
10,000 intervals, shuffled, that all chain into one. Sort and sweep.	0.003 s, and about 0.15 MB, mostly for the sort.
100 intervals that chain into one. Merge until stable.	Under 0.001 s. It is O(n³), so at 10,000 intervals it could take about a trillion steps.