Non-overlapping Intervals

Given an array of intervals where intervals[i] = [start, end], return the minimum number of intervals you must remove so that the remaining intervals are non-overlapping.

Two intervals that only touch at an endpoint (e.g. [1, 2] and [2, 3]) are considered non-overlapping.

Hints

· Stuck? Reveal one nudge at a time.

Removing the fewest intervals is the same as keeping the most non-overlapping ones.

That's activity selection — sort by end time and greedily keep compatible intervals.

Since touching is allowed, keep an interval when its start is >= the last kept end.

Common doubts

Every interval is either kept or removed, so removals = n - kept. Maximizing kept minimizes removals.

When two intervals overlap you should drop the one that ends later (it blocks more of the timeline). Sorting by end makes the greedy keep the earlier-ending one automatically.

Intervals that merely touch at an endpoint don't overlap, so an interval starting exactly at the last kept end is still compatible.

Interview follow-ups

· What an interviewer asks next.

Greedy no longer applies; it becomes weighted interval scheduling — sort by end and DP with binary search for the last compatible interval.

Track, during the greedy, the intervals you drop; those are exactly the ones to remove.

Fun facts

This is activity selection wearing a disguise — the 'remove the fewest' framing is just the complement of the classic 'select the most'.
The same earliest-end greedy underlies interval graph coloring and conflict-free scheduling.

Asked at

AmazonGoogleMicrosoftMeta

Frequently Sometimes Occasionally

Example 1

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Remove [1,3] and the remaining intervals are non-overlapping.

Example 2

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Keep one [1,2] and remove the other two.

Constraints

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

Removing the fewest intervals is the flip side of keeping the most: if you can keep k non-overlapping intervals out of n, you remove n - k. And "keep the most non-overlapping intervals" is exactly activity selection — sort by finish time and take greedily.

Prerequisites

Before you start

· Concepts used directly in the solution.

Activity selection. Keeping the maximum set of non-overlapping intervals by earliest finish time.

Complement counting. Minimizing removals = n minus the most you can keep.

Touching vs overlapping. Sharing only an endpoint does not count as an overlap here.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The rules

“Do intervals that touch at an endpoint overlap?”

No — [1,2] and [2,3] are fine together, so the keep test is start >= last_end.

“Am I removing or keeping?”

Removing the fewest, which equals keeping the most non-overlapping.

The ideal opening — say it like this

Minimum removals equals n minus the maximum non-overlapping set I can keep.

That maximum set is classic activity selection: sort by end time and greedily keep.

Since touching is allowed, I keep an interval whenever its start is at or after the last kept end.

Understand the problem

Worked example — intervals = [[1,2],[2,3],[3,4],[1,3]]

sort by end: [1,2] [1,3] [2,3] [3,4]
[1,2] keep (last_end = 2)
[1,3] 1 >= 2? no  -> remove (removed = 1)
[2,3] 2 >= 2? yes -> keep (last_end = 3)
[3,4] 3 >= 3? yes -> keep (last_end = 4)
answer: 1

Key observations

1Aha

Fewest removed = most kept

You can't remove fewer than n minus the largest non-overlapping subset, and you never need to remove more. So solve the "keep the most" problem and subtract.

2Aha

Earliest finish keeps the most

Sorting by end time and taking each compatible interval is optimal activity selection — the earliest finisher leaves the most room for the rest.

3Aha

Touching is allowed, so use >=

Because intervals sharing only an endpoint don't overlap, an interval fits when start >= last_end (not strictly greater).

Brute force vs optimal

	Longest-chain DP	Earliest-finish greedy
Idea	Best non-overlapping chain ending at each interval	Sort by end, keep each compatible interval
Time	O(n^2)	O(n log n)
Space	O(n)	O(1)

Both compute the maximum kept set; the greedy proves you only need the earliest finisher, and the answer is n minus that. Full code is in the Approaches selector below.

Summary

Key takeaway

Minimum removals = n - (max non-overlapping kept). Sort by end time and greedily keep every interval whose start >= last_end, counting the rest as removals. Earliest-finish selection keeps the most, so this is optimal — O(n log n), O(1) space.

sort intervals by end
last_end = -infinity; removed = 0
for [start, end] in intervals:
    if start >= last_end: last_end = end   # keep
    else: removed += 1                      # overlap -> remove
return removed