How do you solve Merge Intervals using the Sort by Start, then Sweep-Merge (Optimal) approach?

When to use it: The canonical answer. Lead with 'sort by start, then I only ever compare to the last merged interval'. Sort the intervals by start, then walk once keeping a result list whose last element is the 'current' open interval. **Why sorting makes the check one-sided.** After sorting by start, every interval we visit has a start ≥ every interval already processed. So the *only* way the current interval can overlap the existing merged set is by overlapping the most recent merged interval. That collapses the honest two-sided overlap test down to a single comparison: `cur.start last.end`, there's a gap, so `cur` is a brand-new disjoint interval — append it. Otherwise they overlap (or touch), so extend the current interval: `last.end = max(last.end, cur.end)`. **Why `max(last.end, cur.end)` and not just `cur.end`.** A sorted-by-start interval can still be fully *contained* in the current one — e.g. current `[1,10]`, next `[3,5]`. Writing `last.end = cur.end` would shrink `[1,10]` to `[1,5]` and lose coverage. Taking the max keeps whichever end reaches further right. This single `max` is the line most candidates get wrong under pressure. Time complexity: O(n log n). Space complexity: O(n).

Loading…

mediumIntervalsLC #56Asked very often

Merge Intervals

Q: How do you solve Merge Intervals using the Brute Force — Repeatedly Fuse Any Overlapping Pair approach?

When to use it: Mention to show you understand what 'merge' means mechanically — then discard it as quadratic. Without sorting, an overlapping partner could sit anywhere in the list, so the naive idea is to keep scanning all pairs and fuse any two that overlap, repeating until a full pass makes no change. **Why it works.** Overlap is symmetric and 'mergeability' is transitive across a cluster, so repeatedly unioning any overlapping pair eventually collapses each cluster to one interval. The two-sided overlap test `a.start <= b.end && b.start <= a.end` is the honest definition when nothing is sorted. **Why we abandon it.** Every fuse can invalidate earlier comparisons, forcing another full O(n) sweep, and there can be O(n) fuses — so the whole thing is O(n²). The fix is not a smarter pairwise check; it's to *sort first* so that overlapping intervals become adjacent and a single forward pass suffices. Time complexity: O(n²). Space complexity: O(n).

LCPractice

Intervals · 2 of 7 · 8 min

Given an array of intervals where intervals[i] = [startᵢ, endᵢ], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Two intervals overlap if they share any point, including a single shared endpoint — so [1,4] and [4,5] merge into [1,5].

In plain English

You have a messy set of ranges that may overlap in any combination. Collapse every cluster of overlapping ranges into a single range that spans the cluster, and return the cleaned, disjoint, sorted set. The merged set covers exactly the same points as the original.

Examples

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Note: [1,3] and [2,6] overlap (2 ≤ 3) → [1,6]. The other two are disjoint.

Example 2

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Note: They touch at 4. Because touching counts as overlapping, they merge into [1,5].

Example 3

Input: intervals = [[1,4],[2,3]]
Output: [[1,4]]
Note: [2,3] is fully inside [1,4]. Taking max(4,3)=4 keeps the larger interval intact.

Constraints

1 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ startᵢ ≤ endᵢ ≤ 10⁴
Input is NOT guaranteed sorted
The returned list must be sorted and non-overlapping

Clarifying questions4First question: Is the input sorted?Explore questions

Q1.Is the input sorted?
No — that's the key difference from Insert Interval. We pay an O(n log n) sort up front, which is what makes the single sweep correct.
Q2.Do intervals that only touch at an endpoint count as overlapping?
Yes for this problem — [1,4] and [4,5] merge into [1,5]. That means the overlap test uses `<=`, not strict `<`.
Q3.Can one interval be completely inside another?
Yes — [1,10] and [3,5]. When merging we take max of the ends so the bigger interval isn't shrunk by the contained one.
Q4.Can I mutate / sort the input array in place?
Usually fine, and it saves memory. Confirm, but sorting in place is the standard approach here.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Sort the intervals by start, then sweep left-to-right keeping one 'current' merged interval. If the next interval starts at or before the current interval's end, extend the current end to the max of the two ends; otherwise the current interval is final — push it and start a new one. O(n log n) for the sort, O(n) for the sweep.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for 'sort by start, then sweep' on overlapping ranges — and whether you correctly take max(end) when merging instead of blindly using the later interval's end.

Where candidates slip

Comparing each interval to the previous *raw* interval instead of the last *merged* one, or using the new interval's end directly so a fully-contained interval shrinks the merged range.

How to stand out

State why sorting by start makes the overlap check one-sided, handle the contained-interval case explicitly with max(end), and note the O(n log n) is sort-bound so it can't be beaten without sorted input.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Repeatedly Fuse Any Overlapping Pair	`O(n²)`	`O(n)`	Mention to show you understand what 'merge' means mechanically — then discard it as quadratic.	Read
2	Sort by Start, then Sweep-Merge (Optimal)Optimal	`O(n log n)`	`O(n)`	The canonical answer. Lead with 'sort by start, then I only ever compare to the last merged interval'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCollapse overlapping ranges into disjoint onesInput already sorted?Yes, +1 insertNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Repeatedly Fuse Any Overlapping Pair

TimeO(n²)SpaceO(n)

Mention to show you understand what 'merge' means mechanically — then discard it as quadratic.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Two intervals overlap iff a.start ≤ b.end AND b.start ≤ a.end. How would you fuse every overlapping pair with no sorting at all?

2Hint 2Explore hint

Repeatedly scan all pairs; whenever two overlap, replace them with their union and restart.

3Hint 3Explore hint

It's correct but you re-scan the whole set every time you fuse — that's where the quadratic blow-up comes from.

A · Core idea

Without sorting, an overlapping partner could sit anywhere in the list, so the naive idea is to keep scanning all pairs and fuse any two that overlap, repeating until a full pass makes no change.

Why it works. Overlap is symmetric and 'mergeability' is transitive across a cluster, so repeatedly unioning any overlapping pair eventually collapses each cluster to one interval. The two-sided overlap test a.start <= b.end && b.start <= a.end is the honest definition when nothing is sorted.

Why we abandon it. Every fuse can invalidate earlier comparisons, forcing another full O(n) sweep, and there can be O(n) fuses — so the whole thing is O(n²). The fix is not a smarter pairwise check; it's to sort first so that overlapping intervals become adjacent and a single forward pass suffices.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

pass 1: (2,6)&(1,3)

overlap → fuse to [1,6]

State[[1,6],[8,10]]

Final result[[1,6],[8,10]]

C · Code with teaching comments

Reference implementation previewpublic int[][] merge(int[][] intervals) { List<int[]> list = new ArrayList<>(Arrays.asList(intervals)); boolean changed = true; while (changed) { changed = false;Explore the full code

solution.javaJava

Brute Force — Repeatedly Fuse Any Overlapping Pair — reference

2 teaching notes

1
public int[][] merge(int[][] intervals) {
2
    List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
3
    boolean changed = true;
4
    while (changed) {
5
        changed = false;
6
        outer:
7
        for (int a = 0; a < list.size(); a++) {
8
            for (int b = a + 1; b < list.size(); b++) {
9
                int[] x = list.get(a), y = list.get(b);
10
                // Full two-sided overlap test — needed because nothing is sorted.
11
                if (x[0] <= y[1] && y[0] <= x[1]) {
12
                    // Union spans the smaller start to the larger end.
13
                    int[] u = {Math.min(x[0], y[0]), Math.max(x[1], y[1])};
14
                    list.remove(b);
15
                    list.set(a, u);
16
                    changed = true;
17
                    break outer;
18
                }
19
            }
20
        }
21
    }
22
    return list.toArray(new int[list.size()][]);
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

The pain here is that overlaps can hide anywhere, so you keep looking backwards. Sorting by start eliminates 'backwards' entirely: after sorting, if an interval overlaps the current cluster at all, it overlaps the most recent merged interval — so one forward scan is enough.

ComplexityO(n²) time, O(n) space — Each fuse can trigger a fresh O(n) pass and there can be O(n) fuses, giving O(n²). The sorted approach removes the need to ever look backwards.

E · Edge cases and pitfalls5intervals = [[1,4],[2,3]] — Pair overlaps; union = [min(1,2), max(4,3)] = [1,4]. Contained interval doesn't shrink the result.Explore edge cases

Edge cases handled

intervals = [[1,4],[2,3]]Pair overlaps; union = [min(1,2), max(4,3)] = [1,4]. Contained interval doesn't shrink the result.
intervals = [[1,2],[3,4]]No pair overlaps; the first full pass makes no fuse → returns input unchanged.

Pitfalls

Using the later interval's end directly instead of max — shrinks the result on contained intervals.
Forgetting to restart after a fuse — a new union can overlap an interval you already passed.
Treating O(n²) as acceptable just because it passes small cases.

03.2

Approach 2 of 2 · Optimal

Sort by Start, then Sweep-Merge (Optimal)

TimeO(n log n)SpaceO(n)

The canonical answer. Lead with 'sort by start, then I only ever compare to the last merged interval'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If the intervals were sorted by start, where is the only place an overlap with the current cluster can appear?

2Hint 2Explore hint

Sort by start. Keep a result list; for each interval, either it extends the last merged interval (start ≤ last end) or it begins a fresh one.

3Hint 3Explore hint

When it extends, set last.end = max(last.end, cur.end) — the current interval might be entirely inside the last.

A · Core idea

Sort the intervals by start, then walk once keeping a result list whose last element is the 'current' open interval.

Why sorting makes the check one-sided. After sorting by start, every interval we visit has a start ≥ every interval already processed. So the only way the current interval can overlap the existing merged set is by overlapping the most recent merged interval. That collapses the honest two-sided overlap test down to a single comparison: cur.start <= last.end. No need to look backwards, no need to check the start side — sorting bought us that.

The sweep. For each interval cur: if the result is empty or cur.start > last.end, there's a gap, so cur is a brand-new disjoint interval — append it. Otherwise they overlap (or touch), so extend the current interval: last.end = max(last.end, cur.end).

Why `max(last.end, cur.end)` and not just `cur.end`. A sorted-by-start interval can still be fully contained in the current one — e.g. current [1,10], next [3,5]. Writing last.end = cur.end would shrink [1,10] to [1,5] and lose coverage. Taking the max keeps whichever end reaches further right. This single max is the line most candidates get wrong under pressure.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

[1,3]

append — first interval

cur ↓

[1,3]

[0]

[2,6]

[1]

[8,10]

[2]

[15,18]

[3]

Current pointerResolved stateNot processed

Final result[[1,6],[8,10],[15,18]]

C · Code with teaching comments

solution.javaJava

Sort by Start, then Sweep-Merge (Optimal) — optimal

3 teaching notes

1
public int[][] merge(int[][] intervals) {
2
    // Sort by start — this is what makes the overlap check one-sided.
3
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
4
    List<int[]> res = new ArrayList<>();
5
    for (int[] cur : intervals) {
6
        // Strict gap → cur is a new disjoint interval. `<=` would mean overlap.
7
        if (res.isEmpty() || cur[0] > res.get(res.size() - 1)[1]) {
8
            res.add(cur);
9
        } else {
10
            int[] last = res.get(res.size() - 1);
11
            // Extend by the FURTHER end — cur may be fully contained in last.
12
            last[1] = Math.max(last[1], cur[1]);
13
        }
14
    }
15
    return res.toArray(new int[res.size()][]);
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

The whole trick is that sorting localizes overlap. Before sorting, an overlapping partner can be anywhere, forcing O(n²) pair checks; after sorting, it can only be the neighbor you just merged. That 'sort to make the relevant thing adjacent' move is the beating heart of nearly every interval problem — internalize it once and Insert Interval, Non-overlapping Intervals, and both Meeting Rooms variants all fall out of it.

ComplexityO(n log n) time, O(n) space — Sorting is O(n log n) and dominates; the sweep visits each interval once doing O(1) work, O(n). Output (and the sort) need O(n) space.

E · Edge cases and pitfalls5intervals = [[1,4],[4,5]] — Sorted; 4 ≤ 4 (touching counts) → extend to [1,5]. Returns [[1,5]].Explore edge cases

Edge cases handled

intervals = [[1,4],[4,5]]Sorted; 4 ≤ 4 (touching counts) → extend to [1,5]. Returns [[1,5]].
intervals = [[1,4],[2,3]]Sorted; 2 ≤ 4 → extend, max(4,3)=4 → [[1,4]]. Contained interval handled by max.

Pitfalls

Forgetting to sort — the one-sided overlap check is only valid on sorted input.
Writing `last.end = cur.end` instead of `max(...)` — shrinks on contained intervals.
Using `<` instead of `<=` in the merge test — fails to fuse touching intervals like [1,4] and [4,5].

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> res = new ArrayList<>(); for (int[] cur : intervals) { if (res.isEmpty() || cur[0] > res.get(res.size() - 1)[1]) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Using the new interval's end instead of the max

A sorted interval can be fully inside the current one ([1,10] then [3,5]). Assigning cur.end directly shrinks [1,10] to [1,5] and loses coverage.

Explore the code comparison

Don't write this

if cur[0] <= res[-1][1]:
    res[-1][1] = cur[1]            # shrinks on [1,10] then [3,5]

Write this instead

if cur[0] <= res[-1][1]:
    res[-1][1] = max(res[-1][1], cur[1])

Comparing to the previous interval, not the last merged one

Three intervals can chain-merge ([1,5],[2,8],[7,9]). Comparing each to its raw predecessor instead of the growing merged tail breaks the chain.

Explore the code comparison

Don't write this

for (int i = 1; i < intervals.length; i++) {
    if (intervals[i][0] <= intervals[i - 1][1]) { /* uses raw prev */ }
}

Write this instead

int[] last = res.get(res.size() - 1);
if (cur[0] <= last[1]) { last[1] = Math.max(last[1], cur[1]); }

Skipping the sort

The single one-sided overlap test (cur.start <= last.end) is only correct once intervals are sorted by start. On unsorted input it misses overlaps that appear out of order.

Explore the code comparison

Don't write this

res = []
for cur in intervals:           # no sort
    ...

Write this instead

intervals.sort(key=lambda iv: iv[0])
res = []
for cur in intervals:
    ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort by start, then linear sweep-merge

Code pattern to memorize

intervals.sort(by start)
for iv in intervals:
    if res and iv.start <= res[-1].end: res[-1].end = max(res[-1].end, iv.end)
    else: res.append(iv)

Rules to remember

1Sort by start first — without it the sweep is meaningless because a later overlapper could appear anywhere.
2Overlap test after sorting collapses to one comparison: iv.start <= last.end. You never need to check the start side.
3When merging, take max(last.end, iv.end) — the next interval can be fully inside the current one (don't shrink the end).
4Compare against the last merged interval, not the previous raw interval — merging can keep extending the same bucket.
5Use <= (not <) so touching intervals like [1,4] and [4,5] fuse into [1,5].

Use this pattern when

A pile of unsorted intervals you must collapse into disjoint ones
Calendar consolidation, free/busy merging, range coalescing
Any 'combine overlapping ranges' phrasing
Output must itself be sorted and non-overlapping

Choose another pattern when

Input is already sorted + one insert → Insert Interval's O(n) sweep (LC 57)
You only need the count of rooms / max overlap → sweep-line or heap, not a merge
You must remove the fewest intervals to make them disjoint → greedy by end (LC 435)
Endpoints are exclusive → switch the overlap test to strict `<`

Interview takeaway

Sorting by start is what turns interval problems from O(n²) pair-checking into an O(n) sweep — after sorting, the only interval that can overlap the current one is the next one. Merge Intervals is THE template; Insert Interval, Non-overlapping Intervals, and Meeting Rooms are all variations on this sweep.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Interval Sweep. Sort by start, then merge against the last kept interval. The foundational template for Insert Interval, Non-overlapping Intervals, and both Meeting Rooms problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Insert Interval

Continue · Next problem

Non-overlapping Intervals

mediumIntervalsLC #56Asked very often

Merge Intervals

LCPractice

Intervals · 2 of 7 · 8 min

Two intervals overlap if they share any point, including a single shared endpoint — so [1,4] and [4,5] merge into [1,5].

In plain English

Examples

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Note: [1,3] and [2,6] overlap (2 ≤ 3) → [1,6]. The other two are disjoint.

Example 2

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Note: They touch at 4. Because touching counts as overlapping, they merge into [1,5].

Example 3

Input: intervals = [[1,4],[2,3]]
Output: [[1,4]]
Note: [2,3] is fully inside [1,4]. Taking max(4,3)=4 keeps the larger interval intact.

Constraints

1 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ startᵢ ≤ endᵢ ≤ 10⁴
Input is NOT guaranteed sorted
The returned list must be sorted and non-overlapping

Clarifying questions4First question: Is the input sorted?Explore questions

Q1.Is the input sorted?
No — that's the key difference from Insert Interval. We pay an O(n log n) sort up front, which is what makes the single sweep correct.
Q2.Do intervals that only touch at an endpoint count as overlapping?
Yes for this problem — [1,4] and [4,5] merge into [1,5]. That means the overlap test uses `<=`, not strict `<`.
Q3.Can one interval be completely inside another?
Yes — [1,10] and [3,5]. When merging we take max of the ends so the bigger interval isn't shrunk by the contained one.
Q4.Can I mutate / sort the input array in place?
Usually fine, and it saves memory. Confirm, but sorting in place is the standard approach here.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for 'sort by start, then sweep' on overlapping ranges — and whether you correctly take max(end) when merging instead of blindly using the later interval's end.

Where candidates slip

Comparing each interval to the previous *raw* interval instead of the last *merged* one, or using the new interval's end directly so a fully-contained interval shrinks the merged range.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Repeatedly Fuse Any Overlapping Pair	`O(n²)`	`O(n)`	Mention to show you understand what 'merge' means mechanically — then discard it as quadratic.	Read
2	Sort by Start, then Sweep-Merge (Optimal)Optimal	`O(n log n)`	`O(n)`	The canonical answer. Lead with 'sort by start, then I only ever compare to the last merged interval'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Repeatedly Fuse Any Overlapping Pair

TimeO(n²)SpaceO(n)

Mention to show you understand what 'merge' means mechanically — then discard it as quadratic.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Two intervals overlap iff a.start ≤ b.end AND b.start ≤ a.end. How would you fuse every overlapping pair with no sorting at all?

2Hint 2Explore hint

Repeatedly scan all pairs; whenever two overlap, replace them with their union and restart.

3Hint 3Explore hint

It's correct but you re-scan the whole set every time you fuse — that's where the quadratic blow-up comes from.

A · Core idea

Without sorting, an overlapping partner could sit anywhere in the list, so the naive idea is to keep scanning all pairs and fuse any two that overlap, repeating until a full pass makes no change.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

pass 1: (2,6)&(1,3)

overlap → fuse to [1,6]

State[[1,6],[8,10]]

Final result[[1,6],[8,10]]

C · Code with teaching comments

solution.javaJava

Brute Force — Repeatedly Fuse Any Overlapping Pair — reference

2 teaching notes

1
public int[][] merge(int[][] intervals) {
2
    List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
3
    boolean changed = true;
4
    while (changed) {
5
        changed = false;
6
        outer:
7
        for (int a = 0; a < list.size(); a++) {
8
            for (int b = a + 1; b < list.size(); b++) {
9
                int[] x = list.get(a), y = list.get(b);
10
                // Full two-sided overlap test — needed because nothing is sorted.
11
                if (x[0] <= y[1] && y[0] <= x[1]) {
12
                    // Union spans the smaller start to the larger end.
13
                    int[] u = {Math.min(x[0], y[0]), Math.max(x[1], y[1])};
14
                    list.remove(b);
15
                    list.set(a, u);
16
                    changed = true;
17
                    break outer;
18
                }
19
            }
20
        }
21
    }
22
    return list.toArray(new int[list.size()][]);
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(n) space — Each fuse can trigger a fresh O(n) pass and there can be O(n) fuses, giving O(n²). The sorted approach removes the need to ever look backwards.

E · Edge cases and pitfalls5intervals = [[1,4],[2,3]] — Pair overlaps; union = [min(1,2), max(4,3)] = [1,4]. Contained interval doesn't shrink the result.Explore edge cases

Edge cases handled

intervals = [[1,4],[2,3]]Pair overlaps; union = [min(1,2), max(4,3)] = [1,4]. Contained interval doesn't shrink the result.
intervals = [[1,2],[3,4]]No pair overlaps; the first full pass makes no fuse → returns input unchanged.

Pitfalls

Using the later interval's end directly instead of max — shrinks the result on contained intervals.
Forgetting to restart after a fuse — a new union can overlap an interval you already passed.
Treating O(n²) as acceptable just because it passes small cases.

03.2

Approach 2 of 2 · Optimal

Sort by Start, then Sweep-Merge (Optimal)

TimeO(n log n)SpaceO(n)

The canonical answer. Lead with 'sort by start, then I only ever compare to the last merged interval'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If the intervals were sorted by start, where is the only place an overlap with the current cluster can appear?

2Hint 2Explore hint

Sort by start. Keep a result list; for each interval, either it extends the last merged interval (start ≤ last end) or it begins a fresh one.

3Hint 3Explore hint

When it extends, set last.end = max(last.end, cur.end) — the current interval might be entirely inside the last.

A · Core idea

Sort the intervals by start, then walk once keeping a result list whose last element is the 'current' open interval.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

[1,3]

append — first interval

cur ↓

[1,3]

[0]

[2,6]

[1]

[8,10]

[2]

[15,18]

[3]

Current pointerResolved stateNot processed

Final result[[1,6],[8,10],[15,18]]

C · Code with teaching comments

solution.javaJava

Sort by Start, then Sweep-Merge (Optimal) — optimal

3 teaching notes

1
public int[][] merge(int[][] intervals) {
2
    // Sort by start — this is what makes the overlap check one-sided.
3
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
4
    List<int[]> res = new ArrayList<>();
5
    for (int[] cur : intervals) {
6
        // Strict gap → cur is a new disjoint interval. `<=` would mean overlap.
7
        if (res.isEmpty() || cur[0] > res.get(res.size() - 1)[1]) {
8
            res.add(cur);
9
        } else {
10
            int[] last = res.get(res.size() - 1);
11
            // Extend by the FURTHER end — cur may be fully contained in last.
12
            last[1] = Math.max(last[1], cur[1]);
13
        }
14
    }
15
    return res.toArray(new int[res.size()][]);
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n log n) time, O(n) space — Sorting is O(n log n) and dominates; the sweep visits each interval once doing O(1) work, O(n). Output (and the sort) need O(n) space.

E · Edge cases and pitfalls5intervals = [[1,4],[4,5]] — Sorted; 4 ≤ 4 (touching counts) → extend to [1,5]. Returns [[1,5]].Explore edge cases

Edge cases handled

intervals = [[1,4],[4,5]]Sorted; 4 ≤ 4 (touching counts) → extend to [1,5]. Returns [[1,5]].
intervals = [[1,4],[2,3]]Sorted; 2 ≤ 4 → extend, max(4,3)=4 → [[1,4]]. Contained interval handled by max.

Pitfalls

Forgetting to sort — the one-sided overlap check is only valid on sorted input.
Writing `last.end = cur.end` instead of `max(...)` — shrinks on contained intervals.
Using `<` instead of `<=` in the merge test — fails to fuse touching intervals like [1,4] and [4,5].

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Using the new interval's end instead of the max

A sorted interval can be fully inside the current one ([1,10] then [3,5]). Assigning cur.end directly shrinks [1,10] to [1,5] and loses coverage.

Explore the code comparison

Don't write this

if cur[0] <= res[-1][1]:
    res[-1][1] = cur[1]            # shrinks on [1,10] then [3,5]

Write this instead

if cur[0] <= res[-1][1]:
    res[-1][1] = max(res[-1][1], cur[1])

Comparing to the previous interval, not the last merged one

Three intervals can chain-merge ([1,5],[2,8],[7,9]). Comparing each to its raw predecessor instead of the growing merged tail breaks the chain.

Explore the code comparison

Don't write this

for (int i = 1; i < intervals.length; i++) {
    if (intervals[i][0] <= intervals[i - 1][1]) { /* uses raw prev */ }
}

Write this instead

int[] last = res.get(res.size() - 1);
if (cur[0] <= last[1]) { last[1] = Math.max(last[1], cur[1]); }

Skipping the sort

The single one-sided overlap test (cur.start <= last.end) is only correct once intervals are sorted by start. On unsorted input it misses overlaps that appear out of order.

Explore the code comparison

Don't write this

res = []
for cur in intervals:           # no sort
    ...

Write this instead

intervals.sort(key=lambda iv: iv[0])
res = []
for cur in intervals:
    ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort by start, then linear sweep-merge

Code pattern to memorize

intervals.sort(by start)
for iv in intervals:
    if res and iv.start <= res[-1].end: res[-1].end = max(res[-1].end, iv.end)
    else: res.append(iv)

Rules to remember

1Sort by start first — without it the sweep is meaningless because a later overlapper could appear anywhere.
2Overlap test after sorting collapses to one comparison: iv.start <= last.end. You never need to check the start side.
3When merging, take max(last.end, iv.end) — the next interval can be fully inside the current one (don't shrink the end).
4Compare against the last merged interval, not the previous raw interval — merging can keep extending the same bucket.
5Use <= (not <) so touching intervals like [1,4] and [4,5] fuse into [1,5].

Use this pattern when

A pile of unsorted intervals you must collapse into disjoint ones
Calendar consolidation, free/busy merging, range coalescing
Any 'combine overlapping ranges' phrasing
Output must itself be sorted and non-overlapping

Choose another pattern when

Input is already sorted + one insert → Insert Interval's O(n) sweep (LC 57)
You only need the count of rooms / max overlap → sweep-line or heap, not a merge
You must remove the fewest intervals to make them disjoint → greedy by end (LC 435)
Endpoints are exclusive → switch the overlap test to strict `<`

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Insert Interval

Continue · Next problem

Non-overlapping Intervals