#56 Merge Intervals

Mediumsolve on LeetCode ↗

frequently reported atWalmart Bloomberg Adobe Meta Apple Netflix

the problem

In plain words

Merge all overlapping intervals and return the non-overlapping intervals that cover exactly the same ranges.

in intervals = [[1,3],[2,6],[8,10],[15,18]]

out [[1,6],[8,10],[15,18]]

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

out [[1,5]]

Touching intervals count as overlapping here.

in intervals = [[4,7],[1,4]]

out [[1,7]]

The input isn't sorted.

1 ≤ intervals.length ≤ 10⁴
0 ≤ start ≤ end ≤ 10⁴

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternInterval merging (sort by start)

After sorting by start, an interval can only overlap the last group you built. Either it stretches that group, or it starts a new one.

solutions

From brute force to optimal

Repeatedly scan all pairs. Merge the first overlapping pair found, then rescan.

Scan every pair (i, j).
If they overlap, replace them with their union and restart.
Stop when a full scan finds nothing; sort the result.

timeO(n³)

Up to n merges, each found by an O(n²) pair scan.

spaceO(n)

The working list.

javajava.util.*

1class Solution {2    public int[][] merge(int[][] intervals) {3        List<int[]> list = new ArrayList<>();4        for (int[] iv : intervals) list.add(new int[] {iv[0], iv[1]});5        boolean changed = true;6        while (changed) {                                   // repeat until no pair overlaps7            changed = false;8            search:9            for (int i = 0; i < list.size(); i++) {10                for (int j = i + 1; j < list.size(); j++) {11                    int[] a = list.get(i), b = list.get(j);12                    if (a[0] <= b[1] && b[0] <= a[1]) {     // overlap (touching counts)13                        a[0] = Math.min(a[0], b[0]);14                        a[1] = Math.max(a[1], b[1]);15                        list.remove(j);16                        changed = true;17                        break search;18                    }19                }20            }21        }22        list.sort((x, y) -> Integer.compare(x[0], y[0]));23        return list.toArray(new int[0][]);24    }25}

Sort by start. For each interval: if it starts after the last group ends, open a new group; otherwise stretch the group's end.

Sort by start.
If merged is empty or iv[0] > last[1], append a copy.
Else last[1] = max(last[1], iv[1]).

timeO(n log n)

The sort dominates; the sweep is O(n).

spaceO(n)

The output list, plus the sort's buffer.

javajava.util.*

1class Solution {2    public int[][] merge(int[][] intervals) {3        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));4        List<int[]> merged = new ArrayList<>();5        for (int[] iv : intervals) {6            int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);7            if (last == null || iv[0] > last[1]) { // gap after the last group?8                merged.add(new int[] {iv[0], iv[1]}); // start a new group9            } else {10                last[1] = Math.max(last[1], iv[1]); // overlap: stretch the group11            }12        }13        return merged.toArray(new int[0][]);14    }15}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int[][] merge(int[][] intervals) {3        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));4        List<int[]> merged = new ArrayList<>();5        for (int[] iv : intervals) {6            int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);7            if (last == null || iv[0] > last[1]) { // gap after the last group?8                merged.add(new int[] {iv[0], iv[1]}); // start a new group9            } else {10                last[1] = Math.max(last[1], iv[1]); // overlap: stretch the group11            }12        }13        return merged.toArray(new int[0][]);14    }15}

in the room

How to say it in the interview

talk track

Ask: do touching intervals merge? Is the input sorted? Can I modify it?
Explain why only the last group matters: everything earlier ends before the last group starts.
Draw intervals on a number line. The sorted sweep becomes obvious.

traps

last[1] = iv[1] instead of max breaks on nested intervals like [1,10], [2,3].
Using >= in the gap check stops [1,4] and [4,5] from merging.
Comparator (a, b) -> a[0] - b[0] is fine for these constraints, but Integer.compare is the safe habit (subtraction can overflow).

what they ask next

Follow-ups

Intervals arrive as a stream?

Keep them in a TreeMap<start, end>. Use floorKey/ceilingKey to find neighbours and merge them in O(log n) per insert.

Already sorted, and you get one new interval?

That's LC 57 Insert Interval. Do it in O(n) with no sort.

Minimum meeting rooms (LC 253)?

Sort starts and ends separately (or use a min-heap of end times) and count overlaps. See Meeting Rooms II in this chapter.

before you submit

Edge cases to test

Touching [1,4] and [4,5] → [1,5].
Nested [1,10] and [2,3] → [1,10]: take the max end.
Unsorted input like [[4,7],[1,4]] → [[1,7]].
Single points such as [5,5] are valid intervals.

practise next