Example 1
ready- Input
intervals = [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 1, 3 ] ]- Expected
1- Why
- remove [1, 3]; the three shorter intervals then touch without overlapping
Non-overlapping Intervals
35 min · eraseOverlapIntervals()mediumOpen in LeetCode #435 ↗
A room has too many bookings, and some of them collide. You don't get to move a booking; you can only cancel as few as possible until the schedule is conflict-free.
Given intervals, return the minimum number of intervals to remove so every remaining
pair is non-overlapping.
Endpoints may touch without a conflict. [1, 2] followed by [2, 3] is valid because
the first interval ends exactly when the second begins.
A few ground rules:
- Every interval is
[start, end]withstart < end. - The input may arrive in any order and may contain duplicates.
- You return only the number removed, not the surviving intervals.
Constraints
1 <= intervals.length <= 100_000- Every interval has exactly two integers:
[start, end]. -50_000 <= start < end <= 50_000
Hints
Flip what you count
Minimizing removals is the same as maximizing how many compatible intervals you
keep. The answer is total - kept.
Which booking leaves room?
When several intervals compete, keeping the one that ends earliest leaves the most room for everything that follows.
Sort by the decision boundary
Sort by end time. Keep an interval when its start is at least the end of the last kept interval; equality is allowed because touching isn't overlap here.
Follow-up
Can you give an exchange argument: if an optimal schedule keeps a later-ending interval first, why can you replace it with the earliest-ending choice without losing capacity?
Visible cases
Examples
Example 2
ready- Input
intervals = [ [ 1, 2 ], [ 1, 2 ], [ 1, 2 ] ]- Expected
2- Why
- only one of three identical ranges can remain
Example 3
ready- Input
intervals = [ [ 1, 2 ], [ 2, 3 ] ]- Expected
0- Why
- touching at endpoint 2 doesn't create an overlap
Interview signal
Asked at
AmazonGoogleMeta
Longest compatible set DP
Flip the goal first. If the largest non-overlapping subset contains kept intervals,
then the minimum removals equal len(intervals) - kept.
Sort by end. Let best[i] be the largest compatible set that ends with interval i.
Look back at every earlier interval j; when its end is at most i's start, it can come
before i.
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
ordered = sorted(intervals, key=lambda interval: interval[1])
best = [1] * len(ordered)
for i in range(len(ordered)):
for j in range(i):
if ordered[j][1] <= ordered[i][0]:
best[i] = max(best[i], best[j] + 1)
kept = max(best)
return len(intervals) - keptThe table proves the answer, but checking every earlier interval repeats a lot of work.
Time O(n²) after sorting. Space O(n) for the DP table and sorted copy.
Earliest-end greedy
A greedy choice takes the locally best option and never revisits it. Here, sort by end and keep the first compatible interval. An earlier finish can only leave at least as much room as a later finish.
Suppose an optimal schedule starts with some later-ending interval. Replacing that first choice with the earliest-ending compatible interval can't block any later booking: the replacement finishes no later. That exchange keeps the schedule just as large, so the greedy first choice belongs to an optimal answer. Repeat the same argument for the remaining suffix.
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
ordered = sorted(intervals, key=lambda interval: interval[1])
kept = 0
previous_end = float("-inf")
for start, end in ordered:
if start >= previous_end:
kept += 1
previous_end = end
return len(intervals) - keptThe comparison is start >= previous_end. Equality keeps both intervals because
touching endpoints don't overlap in this problem.
Time O(n log n) for sorting, followed by one pass. Space O(n) for the sorted copy.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
1
Run: visible + custom · Submit: full suite