Non-overlapping Intervals — Solution

Problem

Given a list of intervals, return the minimum number of intervals you must remove so that none of the remaining intervals overlap. Two intervals that share only a single endpoint (like [1,2] and [2,3]) are not considered overlapping.

• Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
• Output: 1
• Explanation: Removing [1,3] leaves [[1,2],[2,3],[3,4]], which have no overlaps.

Counter-example: [[1,2],[1,2],[1,2]] → Output 2, because three identical intervals can only keep one.

Intuition

The problem is equivalent to keeping as many intervals as possible with no overlaps — the answer is just total minus kept. The key insight is that if we sort by end time and always greedily accept the next interval that doesn't conflict, we leave the most room for future intervals. An interval that ends sooner can never block more future choices than one ending later.

Solution — Greedy (Sort by End Time)

Sort intervals by end time, then scan left to right. Keep a boundary marking where the last accepted interval ends. Any interval whose start falls before that boundary overlaps with the most recently kept interval and must be removed; any interval starting at or after the boundary is safe to keep.

1. Sort intervals by end time.
2. Set prev_end to the end of the first interval and intervals_to_remove = 0.
3. For each remaining interval (index 1 onward):
   • If its start is strictly less than prev_end, it overlaps — increment intervals_to_remove.
   • Otherwise, accept it and update prev_end to its end.
4. Return intervals_to_remove.

1def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
2    intervals.sort(key=lambda interval: interval[1])  # earlier end = more room for future intervals
3
4    prev_end = intervals[0][1]
5    intervals_to_remove = 0
6
7    for i in range(1, len(intervals)):
8        if intervals[i][0] < prev_end:  # starts before boundary → overlaps, must remove
9            intervals_to_remove += 1
10        else:
11            prev_end = intervals[i][1]  # no overlap: accept and advance the boundary
12
13    return intervals_to_remove

Time: O(n log n) — dominated by sorting; the scan is a single O(n) pass.
Space: O(1) — no auxiliary data structures beyond the sorted input.

Complexity Summary

Common Mistakes

• Sorting by start time instead of end time — an interval that starts earliest might extend far into the future and block many compatible intervals; sorting by end time is what guarantees we always pick the choice that leaves the most room.
• Using <= instead of < for the overlap check — intervals sharing only one endpoint (like [1,2] and [2,3]) are explicitly not overlapping per the problem's definition, so the condition must be intervals[i][0] < prevEnd, not <=.
• Removing the current interval when you should remove the longer one — when an overlap is detected, the greedy strategy already ensured we kept the interval with the earlier end, so the current interval (which ends later or at the same time) is always the one to discard.
• Forgetting to update prev_end only when keeping an interval — if you update prev_end unconditionally on every iteration, you lose track of the actual boundary and incorrectly allow later overlaps.
• Tracking kept intervals and forgetting to subtract — it's valid to count kept intervals and return n - kept, but forgetting the subtraction is a silent logic error that returns a completely wrong answer.

Related Problems

• merge-intervals — applies the same sort-by-start approach but merges overlapping intervals into one instead of counting removals
• insert-interval — requires merging a new interval into an already-sorted list using the same start/end overlap logic
• partition-labels — greedy expansion of a boundary (last occurrence of each character) to form non-overlapping partitions, structurally identical to advancing prev_end
• gas-station — greedy single-pass that resets the candidate start whenever a constraint is violated, analogous to skipping an interval that breaks the non-overlap rule
• jump-game — greedy scan maintaining a running maximum reach, which plays the same role as prev_end — a boundary that extends forward as valid choices are accepted