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.

How to spot this pattern

Classic activity selection: sort by end time and keep every interval that starts after the last kept one ends. Ending earliest leaves the most room for what follows, which is the exchange argument that makes this greedy optimal.

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

▶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

Common pitfalls

Sorting by start time

✗ Wrong

intervals.sort(key=lambda x: x[0])

✓ Right

intervals.sort(key=lambda x: x[1])

A long interval starting early blocks everything behind it. Sorting by end time means each kept interval frees the maximum remaining space, which is exactly what maximises the count kept.

Treating touching intervals as overlapping

✗ Wrong

if s > lastEnd:

✓ Right

if s >= lastEnd:

[1,2] and [2,3] share only an endpoint and can both be kept. The strict test removes one unnecessarily and reports a higher removal count than needed.

Updating lastEnd when dropping an interval

✗ Wrong

else:
    removed += 1
    lastEnd = e

✓ Right

else:
    removed += 1

A removed interval isn't in the schedule, so it can't constrain what comes next — and since the list is sorted by end, its end is no earlier than the one already kept. Updating would only make the frontier worse.

06

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.

07

Complexity

Time

O(n log n)

Space

O(1)

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