Loading…

mediumIntervalsLC #435Sometimes asked

Non-overlapping Intervals

Q: How do you solve Non-overlapping Intervals using the Sort by Start + DP (Longest Non-overlapping Chain) approach?

When to use it: Mention as the 'safe DP' if you don't yet trust the greedy — then point out it's O(n²) and the greedy beats it. Recast the problem as 'find the maximum set of mutually non-overlapping intervals', which is exactly a Longest Increasing Subsequence over intervals ordered by start. **The DP recurrence.** Sort by start. Define `dp[i]` as the size of the largest compatible chain whose last interval is `i`. For each `i`, look at every earlier `j` whose end is ≤ interval `i`'s start (so they don't overlap) and take the best: `dp[i] = 1 + max(dp[j])`. The biggest `dp[i]` is the maximum number you can keep, so the answer is `n − max(dp)`. **Why it's correct but heavy.** This is the brute-force-but-principled way to compute the max keep set — it never assumes anything clever, just tries all chains. The cost is the nested scan: O(n²). For n up to 10⁵ that's 10¹⁰ operations — far too slow. It's worth stating to show you see the problem's structure, then immediately reach for the greedy that computes the same maximum in one pass. Time complexity: O(n²). Space complexity: O(n).

Q: How do you solve Non-overlapping Intervals using the Greedy — Sort by End, Keep Earliest-Finishing (Optimal) approach?

When to use it: The answer they want. Lead with 'this is activity selection: sort by end and greedily keep the earliest finisher'. Sort the intervals by **end** time, then sweep once. Track `prevEnd` (the end of the last interval we decided to keep) and a `kept` counter. For each interval, if its start is `>= prevEnd` it doesn't conflict with anything we've kept, so keep it: increment `kept` and set `prevEnd` to this interval's end. Otherwise it overlaps a kept interval — 'remove' it by simply doing nothing. The answer is `n − kept`. **Why sort by END, not start.** This is the activity-selection insight. Among intervals competing for the same slice of time, the one that *finishes earliest* leaves the most room for everything after it. So greedily committing to the earliest-finishing compatible interval is never a mistake — any other choice ends at least as late and can only block more future intervals. Sorting by end puts the earliest finisher first at every decision point, so a single forward scan makes the optimal choice each time. **Why removing the later-finisher on conflict is safe.** When the current interval starts before `prevEnd`, two intervals fight for overlapping time. We already kept the one that ends earlier (it came first in end-order), so we discard the current (later-ending) one. Dropping the later finisher can only help future intervals, never hurt them — that's the exchange argument that proves the greedy optimal. **Why count keepers, not removals.** Counting removals directly forces you to reason about *which* overlapper to drop in a cluster, which is fiddly. Counting keepers is a clean invariant — 'is this compatible with the last survivor?' — and `removals = n − kept` falls out for free. Time complexity: O(n log n). Space complexity: O(1).

LCPractice

Intervals · 3 of 7 · 8 min

Given an array of intervals where intervals[i] = [startᵢ, endᵢ], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Intervals that only touch at a point, like [1,2] and [2,3], are considered non-overlapping — you do not need to remove either.

In plain English

You want to throw away as few intervals as possible so the survivors don't overlap. Equivalently — and more usefully — you want to keep as MANY non-overlapping intervals as possible. Once you've found the maximum keepable set, the removals are just everything else.

Examples

Example 1

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Note: Remove [1,3] and the rest ([1,2],[2,3],[3,4]) are non-overlapping. One removal.

Example 2

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Note: All three are identical and mutually overlapping. Keep one, remove two.

Example 3

Input: intervals = [[1,2],[2,3]]
Output: 0
Note: They only touch at 2 — non-overlapping. Remove nothing.

Constraints

1 ≤ intervals.length ≤ 10⁵
intervals[i].length == 2
-5·10⁴ ≤ startᵢ < endᵢ ≤ 5·10⁴
An interval always has start < end (no zero-length intervals)

Clarifying questions4First question: Do touching intervals count as overlapping?Explore questions

Q1.Do touching intervals count as overlapping?
No — [1,2] and [2,3] are fine and both can stay. That means the 'compatible' test is start >= prevEnd (with >=, not strict >).
Q2.Should I return the removed intervals or just the count?
Just the count of removals. Internally I'll count keepers and subtract from n.
Q3.Is the input sorted?
No. I'll sort it — by END time, which is the crux of the greedy.
Q4.Can two intervals be identical?
Yes. Identical intervals overlap each other, so all but one must be removed — the greedy handles that naturally.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

This is the classic activity-selection greedy in disguise. Sort by END time, then keep every interval that starts at or after the last kept interval's end. Each kept interval is a 'survivor'; the answer is n − survivors, the number you had to delete. O(n log n) for the sort, O(n) for the scan.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize this as activity selection and sort by END time, instead of sorting by start and trying to reason about which overlapper to delete.

Where candidates slip

Sorting by start and then deleting greedily — it's tempting but you can't cleanly decide which interval to drop. The clean greedy needs end-time ordering, plus the trap of counting removals directly instead of keepers.

How to stand out

Reframe to 'maximize non-overlapping count', justify why earliest-finish is the optimal greedy (exchange argument), and note the start-sort variant works too if you delete the later-ending interval on conflict.

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	Sort by Start + DP (Longest Non-overlapping Chain)	`O(n²)`	`O(n)`	Mention as the 'safe DP' if you don't yet trust the greedy — then point out it's O(n²) and the greedy beats it.	Read
2	Greedy — Sort by End, Keep Earliest-Finishing (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want. Lead with 'this is activity selection: sort by end and greedily keep the earliest finisher'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewWhat do you do with overlaps?Merge them, or remove some?MergeRemove fewestExplore 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

Sort by Start + DP (Longest Non-overlapping Chain)

TimeO(n²)SpaceO(n)

Mention as the 'safe DP' if you don't yet trust the greedy — then point out it's O(n²) and the greedy beats it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Reframe: keep the most non-overlapping intervals, then removals = n − kept. Does that look like a known sequence problem?

2Hint 2Explore hint

Sort by start. Let dp[i] = the largest non-overlapping set ending with interval i. It's Longest Increasing Subsequence on intervals.

3Hint 3Explore hint

dp[i] = 1 + max(dp[j]) over all j < i where intervals[j].end <= intervals[i].start. The answer is n − max(dp).

A · Core idea

Recast the problem as 'find the maximum set of mutually non-overlapping intervals', which is exactly a Longest Increasing Subsequence over intervals ordered by start.

The DP recurrence. Sort by start. Define dp[i] as the size of the largest compatible chain whose last interval is i. For each i, look at every earlier j whose end is ≤ interval i's start (so they don't overlap) and take the best: dp[i] = 1 + max(dp[j]). The biggest dp[i] is the maximum number you can keep, so the answer is n − max(dp).

Why it's correct but heavy. This is the brute-force-but-principled way to compute the max keep set — it never assumes anything clever, just tries all chains. The cost is the nested scan: O(n²). For n up to 10⁵ that's 10¹⁰ operations — far too slow. It's worth stating to show you see the problem's structure, then immediately reach for the greedy that computes the same maximum in one pass.

B · Visual dry run

Interactive dry run

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

intervals = [[1,2],[2,3],[3,4],[1,3]] (sorted by start: [[1,2],[1,3],[2,3],[3,4]])

[1,2]

no earlier compatible → dp=1

Statedp=[1]

Final resultn − max(dp) = 4 − 3 = 1

C · Code with teaching comments

Reference implementation previewpublic int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); int n = intervals.length, best = 0; int[] dp = new int[n]; for (int i = 0; i < n; i++) {Explore the full code

solution.javaJava

Sort by Start + DP (Longest Non-overlapping Chain) — reference

2 teaching notes

1
public int eraseOverlapIntervals(int[][] intervals) {
2
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
3
    int n = intervals.length, best = 0;
4
    int[] dp = new int[n];
5
    for (int i = 0; i < n; i++) {
6
        dp[i] = 1;
7
        for (int j = 0; j < i; j++) {
8
            // j is compatible with i when j ends at or before i starts (touching
9
            // allowed).
10
            if (intervals[j][1] <= intervals[i][0]) {
11
                // Extend the best compatible chain ending at j by interval i.
12
                dp[i] = Math.max(dp[i], dp[j] + 1);
13
            }
14
        }
15
        best = Math.max(best, dp[i]);
16
    }
17
    return n - best;
18
}

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

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

Seeing the problem as 'max chain of compatible intervals = LIS' is genuinely useful — it explains why the answer is n − (something maximized). The greedy is just a much faster way to find that same maximum, exploiting the special structure that LIS-in-general doesn't have.

ComplexityO(n²) time, O(n) space — Filling each dp[i] scans all earlier j, so n × n = O(n²). The greedy replaces this whole table with a single counter.

E · Edge cases and pitfalls5intervals = [[1,2],[1,2],[1,2]] — No interval is compatible with another (all overlap); every dp[i]=1, best=1 → 3 − 1 = 2 removals.Explore edge cases

Edge cases handled

intervals = [[1,2],[1,2],[1,2]]No interval is compatible with another (all overlap); every dp[i]=1, best=1 → 3 − 1 = 2 removals.
intervals = [[1,2],[2,3]][1,2] end 2 ≤ 2 → dp=[1,2], best=2 → 2 − 2 = 0 removals.

Pitfalls

O(n²) is far too slow for n = 10⁵ — only present this as a stepping stone.
Using strict `<` for compatibility wrongly treats touching intervals as overlapping.
Forgetting to subtract from n — the DP gives keepers, the answer is removals.

03.2

Approach 2 of 2 · Optimal

Greedy — Sort by End, Keep Earliest-Finishing (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want. Lead with 'this is activity selection: sort by end and greedily keep the earliest finisher'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you could keep only one interval to leave maximum room for others, which would you pick?

2Hint 2Explore hint

Sort by END time. Greedily keep an interval whenever its start is ≥ the end of the last interval you kept.

3Hint 3Explore hint

Count keepers as you go; the answer is n − keepers. The earliest-finishing choice is provably optimal (exchange argument).

A · Core idea

Sort the intervals by end time, then sweep once. Track prevEnd (the end of the last interval we decided to keep) and a kept counter. For each interval, if its start is >= prevEnd it doesn't conflict with anything we've kept, so keep it: increment kept and set prevEnd to this interval's end. Otherwise it overlaps a kept interval — 'remove' it by simply doing nothing. The answer is n − kept.

Why sort by END, not start. This is the activity-selection insight. Among intervals competing for the same slice of time, the one that finishes earliest leaves the most room for everything after it. So greedily committing to the earliest-finishing compatible interval is never a mistake — any other choice ends at least as late and can only block more future intervals. Sorting by end puts the earliest finisher first at every decision point, so a single forward scan makes the optimal choice each time.

Why removing the later-finisher on conflict is safe. When the current interval starts before prevEnd, two intervals fight for overlapping time. We already kept the one that ends earlier (it came first in end-order), so we discard the current (later-ending) one. Dropping the later finisher can only help future intervals, never hurt them — that's the exchange argument that proves the greedy optimal.

Why count keepers, not removals. Counting removals directly forces you to reason about which overlapper to drop in a cluster, which is fiddly. Counting keepers is a clean invariant — 'is this compatible with the last survivor?' — and removals = n − kept falls out for free.

B · Visual dry run

Interactive dry run

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

intervals = [[1,2],[2,3],[3,4],[1,3]] (sorted by end: [[1,2],[1,3],[2,3],[3,4]])

Array state

[1,2]

keep — prevEnd → 2

i ↓

[1,2]

[0]

[1,3]

[1]

[2,3]

[2]

[3,4]

[3]

Current pointerResolved stateNot processed

Final resultn − kept = 4 − 3 = 1

C · Code with teaching comments

solution.javaJava

Greedy — Sort by End, Keep Earliest-Finishing (Optimal) — optimal

3 teaching notes

1
public int eraseOverlapIntervals(int[][] intervals) {
2
    // Sort by END — the earliest finisher comes first at every decision.
3
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
4
    int kept = 0;
5
    long prevEnd = Long.MIN_VALUE;
6
    for (int[] iv : intervals) {
7
        // Compatible with the last survivor (touching allowed) → keep it.
8
        if (iv[0] >= prevEnd) {
9
            kept++;
10
            // Advance the survivor boundary to this interval's end.
11
            prevEnd = iv[1];
12
        }
13
    }
14
    return intervals.length - kept;
15
}

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

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

Earliest-finish-first is the single most reusable greedy in interval scheduling: it's correct precisely because finishing early dominates finishing late (it never closes off more options). Recognize 'maximize compatible intervals' or 'minimize removals to make disjoint' and your hand should reach for sort-by-end before you finish reading the prompt.

ComplexityO(n log n) time, O(1) space — Sorting by end is O(n log n) and dominates; one linear scan with a running prevEnd and counter is O(n) time, O(1) extra space.

E · Edge cases and pitfalls5intervals = [[1,2],[1,2],[1,2]] — Keep first (prevEnd=2); next two start at 1 < 2 → removed. kept=1 → 3 − 1 = 2.Explore edge cases

Edge cases handled

intervals = [[1,2],[1,2],[1,2]]Keep first (prevEnd=2); next two start at 1 < 2 → removed. kept=1 → 3 − 1 = 2.
intervals = [[1,100],[11,22],[1,11],[2,12]]By end: [1,11],[2,12],[11,22],[1,100]. Keep [1,11], skip [2,12], keep [11,22], skip [1,100] → kept=2 → 4 − 2 = 2.

Pitfalls

Sorting by start instead of end — the greedy choice is no longer obviously optimal.
Using strict `>` for the keep test — wrongly removes a touching, non-overlapping interval.
Counting removals directly inside the loop instead of n − kept — error-prone in clusters.

Practice

Try the solution yourself

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

Editable code previewpublic int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); int kept = 0; long prevEnd = Long.MIN_VALUE; for (int[] iv : intervals) {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.

Sorting by start instead of end

The greedy 'keep earliest finisher' is optimal only when you process by end time. Sorting by start leaves you unable to cleanly decide which overlapper to drop.

Explore the code comparison

Don't write this

intervals.sort(key=lambda iv: iv[0])   # by start — wrong greedy

Write this instead

intervals.sort(key=lambda iv: iv[1])   # by end — activity selection

Treating touching intervals as overlapping

[1,2] and [2,3] are non-overlapping for this problem. Using strict > in the keep test removes one of them needlessly and overcounts removals.

Explore the code comparison

Don't write this

if s > prev_end:        # rejects a valid touching interval
    kept += 1; prev_end = e

Write this instead

if s >= prev_end:       # touching is allowed
    kept += 1; prev_end = e

Returning keepers instead of removals

The greedy naturally counts survivors. The question asks for the number removed, so you must subtract from n.

Explore the code comparison

Don't write this

return kept;                       // that's survivors, not removals

Write this instead

return intervals.length - kept;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy activity selection — sort by END, keep earliest-finishing

Code pattern to memorize

intervals.sort(by end)
kept = 0; prevEnd = -inf
for s, e in intervals:
    if s >= prevEnd: kept += 1; prevEnd = e   # survivor
return n - kept

Rules to remember

1Sort by END, not start. The interval that finishes earliest leaves the most room for the rest — that's the greedy choice that's provably optimal.
2Reframe 'minimum removals' as 'maximum keepers': removals = n − maxNonOverlapping. The keep version is the cleaner greedy.
3Keep an interval iff start >= prevEnd. Touching is allowed: [1,2] and [2,3] are non-overlapping, so use >=.
4When intervals overlap, you 'remove' the one that ends later by simply not updating prevEnd — keep the earlier finisher.
5Initialize prevEnd to negative infinity so the first interval is always kept.

Use this pattern when

Minimum deletions / maximum subset so intervals don't overlap
'Schedule the most non-conflicting activities' (activity selection)
Any 'erase the fewest to make disjoint' phrasing
Maximize count of compatible intervals

Choose another pattern when

You must MERGE overlaps, not remove them → sort by start, sweep (LC 56)
You need the number of rooms / max concurrent → heap / sweep-line (LC 253)
You insert one interval into a sorted list → three-phase sweep (LC 57)
Weighted intervals (each has a value to maximize) → this greedy fails; use DP (Weighted Job Scheduling)

Interview takeaway

Sorting by END is the signature of greedy activity selection: the earliest-finishing interval always leaves maximal room for what follows, so keeping it is never wrong. Flip 'minimum removals' to 'maximum keepers' and the whole problem becomes a one-pass count.

Continue

Transfer the pattern to another problem

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

Transferable patternGreedy Activity Selection. Sort by end, keep earliest-finishing, and the answer is n − keepers. The same end-sort greedy solves Burst Balloons and Maximum Length of Pair Chain.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Merge Intervals
Different goal — fuse overlaps rather than delete. Sort by start, sweep-merge.
Minimum Number of Arrows to Burst Balloons
Coming soon
Same end-sort greedy: arrows = number of non-overlapping groups.
Maximum Length of Pair Chain
Coming soon
Literally the 'keep most' side of this problem — sort by end, count chain.
Meeting Rooms II
Counts max concurrency instead of removals — heap of end times.

Same pattern

←

Merge Intervals

Continue · Next problem

Meeting Rooms

mediumIntervalsLC #435Sometimes asked

Non-overlapping Intervals

LCPractice

Intervals · 3 of 7 · 8 min

Given an array of intervals where intervals[i] = [startᵢ, endᵢ], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Intervals that only touch at a point, like [1,2] and [2,3], are considered non-overlapping — you do not need to remove either.

In plain English

Examples

Example 1

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Note: Remove [1,3] and the rest ([1,2],[2,3],[3,4]) are non-overlapping. One removal.

Example 2

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Note: All three are identical and mutually overlapping. Keep one, remove two.

Example 3

Input: intervals = [[1,2],[2,3]]
Output: 0
Note: They only touch at 2 — non-overlapping. Remove nothing.

Constraints

1 ≤ intervals.length ≤ 10⁵
intervals[i].length == 2
-5·10⁴ ≤ startᵢ < endᵢ ≤ 5·10⁴
An interval always has start < end (no zero-length intervals)

Clarifying questions4First question: Do touching intervals count as overlapping?Explore questions

Q1.Do touching intervals count as overlapping?
No — [1,2] and [2,3] are fine and both can stay. That means the 'compatible' test is start >= prevEnd (with >=, not strict >).
Q2.Should I return the removed intervals or just the count?
Just the count of removals. Internally I'll count keepers and subtract from n.
Q3.Is the input sorted?
No. I'll sort it — by END time, which is the crux of the greedy.
Q4.Can two intervals be identical?
Yes. Identical intervals overlap each other, so all but one must be removed — the greedy handles that naturally.

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 recognize this as activity selection and sort by END time, instead of sorting by start and trying to reason about which overlapper to delete.

Where candidates slip

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	Sort by Start + DP (Longest Non-overlapping Chain)	`O(n²)`	`O(n)`	Mention as the 'safe DP' if you don't yet trust the greedy — then point out it's O(n²) and the greedy beats it.	Read
2	Greedy — Sort by End, Keep Earliest-Finishing (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want. Lead with 'this is activity selection: sort by end and greedily keep the earliest finisher'.	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

Sort by Start + DP (Longest Non-overlapping Chain)

TimeO(n²)SpaceO(n)

Mention as the 'safe DP' if you don't yet trust the greedy — then point out it's O(n²) and the greedy beats it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Reframe: keep the most non-overlapping intervals, then removals = n − kept. Does that look like a known sequence problem?

2Hint 2Explore hint

Sort by start. Let dp[i] = the largest non-overlapping set ending with interval i. It's Longest Increasing Subsequence on intervals.

3Hint 3Explore hint

dp[i] = 1 + max(dp[j]) over all j < i where intervals[j].end <= intervals[i].start. The answer is n − max(dp).

A · Core idea

Recast the problem as 'find the maximum set of mutually non-overlapping intervals', which is exactly a Longest Increasing Subsequence over intervals ordered by start.

B · Visual dry run

Interactive dry run

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

intervals = [[1,2],[2,3],[3,4],[1,3]] (sorted by start: [[1,2],[1,3],[2,3],[3,4]])

[1,2]

no earlier compatible → dp=1

Statedp=[1]

Final resultn − max(dp) = 4 − 3 = 1

C · Code with teaching comments

solution.javaJava

Sort by Start + DP (Longest Non-overlapping Chain) — reference

2 teaching notes

1
public int eraseOverlapIntervals(int[][] intervals) {
2
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
3
    int n = intervals.length, best = 0;
4
    int[] dp = new int[n];
5
    for (int i = 0; i < n; i++) {
6
        dp[i] = 1;
7
        for (int j = 0; j < i; j++) {
8
            // j is compatible with i when j ends at or before i starts (touching
9
            // allowed).
10
            if (intervals[j][1] <= intervals[i][0]) {
11
                // Extend the best compatible chain ending at j by interval i.
12
                dp[i] = Math.max(dp[i], dp[j] + 1);
13
            }
14
        }
15
        best = Math.max(best, dp[i]);
16
    }
17
    return n - best;
18
}

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

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

ComplexityO(n²) time, O(n) space — Filling each dp[i] scans all earlier j, so n × n = O(n²). The greedy replaces this whole table with a single counter.

E · Edge cases and pitfalls5intervals = [[1,2],[1,2],[1,2]] — No interval is compatible with another (all overlap); every dp[i]=1, best=1 → 3 − 1 = 2 removals.Explore edge cases

Edge cases handled

intervals = [[1,2],[1,2],[1,2]]No interval is compatible with another (all overlap); every dp[i]=1, best=1 → 3 − 1 = 2 removals.
intervals = [[1,2],[2,3]][1,2] end 2 ≤ 2 → dp=[1,2], best=2 → 2 − 2 = 0 removals.

Pitfalls

O(n²) is far too slow for n = 10⁵ — only present this as a stepping stone.
Using strict `<` for compatibility wrongly treats touching intervals as overlapping.
Forgetting to subtract from n — the DP gives keepers, the answer is removals.

03.2

Approach 2 of 2 · Optimal

Greedy — Sort by End, Keep Earliest-Finishing (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want. Lead with 'this is activity selection: sort by end and greedily keep the earliest finisher'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you could keep only one interval to leave maximum room for others, which would you pick?

2Hint 2Explore hint

Sort by END time. Greedily keep an interval whenever its start is ≥ the end of the last interval you kept.

3Hint 3Explore hint

Count keepers as you go; the answer is n − keepers. The earliest-finishing choice is provably optimal (exchange argument).

A · Core idea

B · Visual dry run

Interactive dry run

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

intervals = [[1,2],[2,3],[3,4],[1,3]] (sorted by end: [[1,2],[1,3],[2,3],[3,4]])

Array state

[1,2]

keep — prevEnd → 2

i ↓

[1,2]

[0]

[1,3]

[1]

[2,3]

[2]

[3,4]

[3]

Current pointerResolved stateNot processed

Final resultn − kept = 4 − 3 = 1

C · Code with teaching comments

solution.javaJava

Greedy — Sort by End, Keep Earliest-Finishing (Optimal) — optimal

3 teaching notes

1
public int eraseOverlapIntervals(int[][] intervals) {
2
    // Sort by END — the earliest finisher comes first at every decision.
3
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
4
    int kept = 0;
5
    long prevEnd = Long.MIN_VALUE;
6
    for (int[] iv : intervals) {
7
        // Compatible with the last survivor (touching allowed) → keep it.
8
        if (iv[0] >= prevEnd) {
9
            kept++;
10
            // Advance the survivor boundary to this interval's end.
11
            prevEnd = iv[1];
12
        }
13
    }
14
    return intervals.length - kept;
15
}

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

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

ComplexityO(n log n) time, O(1) space — Sorting by end is O(n log n) and dominates; one linear scan with a running prevEnd and counter is O(n) time, O(1) extra space.

E · Edge cases and pitfalls5intervals = [[1,2],[1,2],[1,2]] — Keep first (prevEnd=2); next two start at 1 < 2 → removed. kept=1 → 3 − 1 = 2.Explore edge cases

Edge cases handled

intervals = [[1,2],[1,2],[1,2]]Keep first (prevEnd=2); next two start at 1 < 2 → removed. kept=1 → 3 − 1 = 2.
intervals = [[1,100],[11,22],[1,11],[2,12]]By end: [1,11],[2,12],[11,22],[1,100]. Keep [1,11], skip [2,12], keep [11,22], skip [1,100] → kept=2 → 4 − 2 = 2.

Pitfalls

Sorting by start instead of end — the greedy choice is no longer obviously optimal.
Using strict `>` for the keep test — wrongly removes a touching, non-overlapping interval.
Counting removals directly inside the loop instead of n − kept — error-prone in clusters.

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.

Sorting by start instead of end

The greedy 'keep earliest finisher' is optimal only when you process by end time. Sorting by start leaves you unable to cleanly decide which overlapper to drop.

Explore the code comparison

Don't write this

intervals.sort(key=lambda iv: iv[0])   # by start — wrong greedy

Write this instead

intervals.sort(key=lambda iv: iv[1])   # by end — activity selection

Treating touching intervals as overlapping

[1,2] and [2,3] are non-overlapping for this problem. Using strict > in the keep test removes one of them needlessly and overcounts removals.

Explore the code comparison

Don't write this

if s > prev_end:        # rejects a valid touching interval
    kept += 1; prev_end = e

Write this instead

if s >= prev_end:       # touching is allowed
    kept += 1; prev_end = e

Returning keepers instead of removals

The greedy naturally counts survivors. The question asks for the number removed, so you must subtract from n.

Explore the code comparison

Don't write this

return kept;                       // that's survivors, not removals

Write this instead

return intervals.length - kept;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy activity selection — sort by END, keep earliest-finishing

Code pattern to memorize

intervals.sort(by end)
kept = 0; prevEnd = -inf
for s, e in intervals:
    if s >= prevEnd: kept += 1; prevEnd = e   # survivor
return n - kept

Rules to remember

1Sort by END, not start. The interval that finishes earliest leaves the most room for the rest — that's the greedy choice that's provably optimal.
2Reframe 'minimum removals' as 'maximum keepers': removals = n − maxNonOverlapping. The keep version is the cleaner greedy.
3Keep an interval iff start >= prevEnd. Touching is allowed: [1,2] and [2,3] are non-overlapping, so use >=.
4When intervals overlap, you 'remove' the one that ends later by simply not updating prevEnd — keep the earlier finisher.
5Initialize prevEnd to negative infinity so the first interval is always kept.

Use this pattern when

Minimum deletions / maximum subset so intervals don't overlap
'Schedule the most non-conflicting activities' (activity selection)
Any 'erase the fewest to make disjoint' phrasing
Maximize count of compatible intervals

Choose another pattern when

You must MERGE overlaps, not remove them → sort by start, sweep (LC 56)
You need the number of rooms / max concurrent → heap / sweep-line (LC 253)
You insert one interval into a sorted list → three-phase sweep (LC 57)
Weighted intervals (each has a value to maximize) → this greedy fails; use DP (Weighted Job Scheduling)

Interview takeaway

Continue

Transfer the pattern to another problem

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

Transferable patternGreedy Activity Selection. Sort by end, keep earliest-finishing, and the answer is n − keepers. The same end-sort greedy solves Burst Balloons and Maximum Length of Pair Chain.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Merge Intervals
Different goal — fuse overlaps rather than delete. Sort by start, sweep-merge.
Minimum Number of Arrows to Burst Balloons
Coming soon
Same end-sort greedy: arrows = number of non-overlapping groups.
Maximum Length of Pair Chain
Coming soon
Literally the 'keep most' side of this problem — sort by end, count chain.
Meeting Rooms II
Counts max concurrency instead of removals — heap of end times.

Same pattern

←

Merge Intervals

Continue · Next problem

Meeting Rooms