Command Palette

Search for a command to run...

Hectal
Problem 15.1 · IntervalsMedium

Merge Intervals

PatternMerge Intervals

What it teaches: The core interval technique: sort by start and extend the last block while intervals overlap.

Practise it on judges as “Merge Intervals”.

The problem

Given intervals [start, end], merge all overlapping intervals (touching ones count as overlapping) and return the result, sorted by start.

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Example 2

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

Constraints

  • 1 ≤ n ≤ 10⁴
  • 0 ≤ start ≤ end ≤ 10⁴

Pattern clues in the wording

  • → Overlapping ranges to combine
  • → Unsorted input

These clues point to Merge Intervals: Sort intervals by start; each one either overlaps the last merged interval (extend it) or starts a new one.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        return intervals;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
intervals = [[1,3],[2,6],[8,10],[15,18]]
[[1,6],[8,10],[15,18]]
2
intervals = [[1,4],[4,5]]
[[1,5]]

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Optimal: sort and sweep · O(n log n)
1

Optimal: sort and sweep

Time O(n log n) Space O(n)

Sort by start. For each interval, if it starts ≤ the last merged end, extend; else append it.

Approach 1
import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> out = new ArrayList<>();
        for (int[] cur : intervals) {
            if (!out.isEmpty() && cur[0] <= out.get(out.size() - 1)[1]) {
                int[] last = out.get(out.size() - 1);
                last[1] = Math.max(last[1], cur[1]);
            } else {
                out.add(new int[]{cur[0], cur[1]});
            }
        }
        return out.toArray(new int[0][]);
    }
}

Verdict: Standard.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One interval
  • One interval containing all others
  • Touching intervals

Mistakes people make

  • Forgetting to sort.
  • Replacing the end instead of taking the max.

Interview

Follow-up questions

What if intervals arrive one at a time and you must keep them merged?