LeetCode #435 Medium

Non-overlapping Intervals

Return the minimum number of intervals to remove so that the rest are non-overlapping.

intervalsgreedysorting

02

Intuition

💡

Almost everyone sorts by start time first, and it fails — one long interval beginning early crowds out several short ones that would all have fit. Sort by end instead. Removing the fewest is the same as keeping the most, which makes this classic activity selection: whichever interval finishes earliest leaves the most room for everything after it, so keeping it never costs you a better answer. Then greedily keep any interval starting at or after the last kept end.

03

Approach

1

Flip the objective

Minimising removals is maximising the size of a non-overlapping subset. Stated that way it is the meeting-rooms / activity-selection problem, which has a known greedy solution — recognising the equivalence is most of the work.

2

Sort by end time, not start

Sorting by start fails: one very long interval starting early can crowd out several short ones. Sorting by end works because among any set of conflicting intervals, keeping the one that finishes earliest dominates — it leaves a superset of the room any other choice would leave, so no optimal solution is ever lost.

3

Sweep and count conflicts

Track lastEnd, the end of the most recently kept interval. If the next interval starts at or after it, keep it and update lastEnd. Otherwise it clashes — increment the removal count and, crucially, drop this interval rather than the kept one, since the kept one ends no later and is therefore never the worse choice. O(n log n) for the sort, O(n) for the sweep.

04

Solution & live demo

python

▶1class Solution:
▶2    def eraseOverlapIntervals(self, intervals):
▶3        if not intervals:
▶4            return 0
▶5        intervals.sort(key=lambda x: x[1])
▶6        lastEnd = intervals[0][1]
▶7        removed = 0
▶8        for s, e in intervals[1:]:
▶9            if s >= lastEnd:
▶10                lastEnd = e
▶11            else:
▶12                removed += 1
▶13        return removed

05

Edge cases

No overlaps at all

Every interval is kept and 0 is returned.

All intervals identical

One is kept and the remaining n - 1 are removed.

Touching endpoints like [1,2] and [2,3]

Not an overlap under this problem's definition, so the >= comparison keeps both.

Single interval or empty input

Nothing to remove; the answer is 0.

06

Complexity

Time

O(n log n)

Space

O(1)

Sorting dominates. Sorting by start instead of end is the standard wrong answer.