435. Non-overlapping Intervals

435

MediumIntervals and Sweep LineInterval scheduling greedyGreedy: sort by end, keep earliest finisher

Non-overlapping Intervals

Given an array of intervals, return the minimum number of intervals you must remove so that the remaining intervals do not overlap. Intervals that only touch at an endpoint are not considered overlapping.

Open official problem prompt ↗

In plain English

Find the fewest intervals to delete so what remains is mutually disjoint — equivalently, keep the largest possible non-overlapping subset.

Picture it like this

Scheduling the most classes in one room: always pick the class that ends soonest so the room frees up earliest for the next one.

Example

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Why: Removing [1,3] leaves [1,2],[2,3],[3,4], which are all non-overlapping; no single removal fewer works.

Constraints

1 <= intervals.length <= 10^5intervals[i].length == 2-5 * 10^4 <= start_i < end_i <= 5 * 10^4

Pattern lesson

See the pattern, then code

Greedy: sort by end, keep earliest finisher

↗

Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. To pack the most non-overlapping intervals, always keep the one that finishes earliest; it leaves the most room for the intervals that follow.

New words, made simpleKnow these before the algorithm

Activity selection: The greedy problem of choosing the maximum set of mutually compatible intervals.
Earliest finish rule: Among competing intervals, keeping the one with the smallest end maximizes future room.
Removal: An interval discarded because it overlaps one already kept.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Dynamic programming (LIS-style)

Correct but too slow for n up to 10^5.

Sort by start and compute the longest chain of non-overlapping intervals with DP.

Time O(n^2)Space O(n)

Best choiceGreedy by earliest end

The earliest-finish choice is provably optimal and runs in one pass.

Sort by end; keep an interval whenever it starts at or after the last kept end, otherwise remove it.

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

The rule we keep true

Invariant

prev_end is the end of the compatible subset chosen so far that has the smallest possible finishing time for that subset size.

Why this is correct

Reasoning

An exchange argument shows that replacing any optimal solution's first kept interval with the earliest-finishing one never reduces how many intervals fit afterward, so the greedy earliest-end choice yields a maximum non-overlapping set; the removals are simply everything not kept.

The algorithm in three movesSay these aloud before coding

1Sort intervals by end value ascending

sorted by end: [1,2],[1,3],[2,3],[3,4]

2Track the end of the last interval you kept

keep [1,2] end=2; [1,3] start 1<2 remove

3If the next interval starts at or after that end, keep it and update the end

keep [2,3] end=3; keep [3,4] -> removals=1

4Otherwise it overlaps, so count it as a removal

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[1,2]0

[1,3]1

[2,3]2

[3,4]3

1 · Read[[1,2],[2,3],[3,4],[1,3]]

2 · AskOrder by end value?

3 · Update stateprev_end = -inf

4 · Result[1,2],[1,3],[2,3],[3,4]

Key takeaway

Sorted by end, [1,3] starts before the kept end 2 and is the single removal.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Sort by end
Ordering by finishing time is what makes the greedy choice optimal.
2
Lines 5Track last kept end
prev_end represents the boundary the next interval must clear to be compatible.
3
Lines 6-10Keep-or-remove decision
start >= prev_end means no overlap so keep; otherwise increment the removal count.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single interval needs zero removals
All intervals identical (n-1 removals)
Intervals touching at endpoints like [1,2] and [2,3] are NOT overlaps
Already disjoint input returns 0

Common beginner mistakes

Sorting by start instead of end, which breaks optimality on nested intervals
Using > instead of >= and wrongly removing touching intervals
Returning the count kept instead of the count removed

Check your understanding

Why sort by end rather than by start?

Non-overlapping Intervals

Non-overlapping Intervals

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Intervals and Sweep Line