Non-overlapping Intervals (LeetCode 435)

The problem

Given a list of intervals [start, end], return the minimum number of intervals you must remove so that the remaining ones do not overlap. Intervals that only touch (one ends exactly where the next starts) are fine.

Input:  [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Remove [1, 3] and the rest, [1, 2], [2, 3], [3, 4], sit end to end with no overlap.

How to think about it

Start with brute force. Try every subset of intervals, keep the largest subset with no overlaps, and remove the rest. That is O(2ⁿ).

Flip the question. Removing the fewest is the same as keeping the most non-overlapping intervals. That is the classic activity-selection problem.

The key insight: always keep the interval that finishes first. Among all intervals you could pick next, the one with the earliest end leaves the most room for everything after it. Any optimal answer that picks a later-ending interval instead can swap it for the earlier-ending one without losing anything. So sort by end, keep an interval whenever it starts at or after the last kept end, and count every other interval as removed.

Why not sort by start? A long interval that starts early, like [1, 100], would be kept first and block everything. Sorting by end puts it last, where it is correctly discarded.

Which pattern is this? Intervals with a greedy choice. The tell is “minimum to remove” or “maximum that fit without overlap”. Sort by end, not start.

Approach

1. Sort the intervals by end time.
2. Set end = -infinity (the end of the last kept interval) and removed = 0.
3. For each interval [s, e]: if s >= end, keep it and set end = e. Otherwise it overlaps the last kept one, so removed += 1.
4. Return removed.

Solution

def erase_overlap(intervals):
    intervals.sort(key=lambda x: x[1])      # earliest finisher first
    end = float('-inf'); removed = 0
    for s, e in intervals:
        if s >= end: end = e                # fits after the last kept one: keep it
        else: removed += 1                  # overlaps: drop it
    return removed
# erase_overlap([[1,2],[2,3],[3,4],[1,3]]) -> 1

Dry run

Sorted by end: [[1, 2], [2, 3], [1, 3], [3, 4]].

The answer is 1.

Complexity

• Time: O(n log n). Sorting dominates; the sweep is O(n).
• Space: O(1) extra. Sorted in place, two variables.

Edge cases and pitfalls

• Empty list returns 0.
• Already disjoint intervals return 0.
• Touching intervals are allowed. Use s >= end, not s > end; [1, 2] and [2, 3] do not overlap here.
• Identical intervals such as [[1, 2], [1, 2], [1, 2]] return 2: keep one, remove the rest.
• Sorting by start without extra logic gives wrong answers: with [[1, 100], [2, 3], [4, 5]] it would keep [1, 100] and remove 2 instead of 1.

Related problems

• Minimum Number of Arrows to Burst Balloons (LeetCode 452): the same greedy-by-end sweep, counting groups instead of removals.
• Merge Intervals (LeetCode 56): sort by start and merge instead of removing.
• Meeting Rooms (LeetCode 252): the yes/no version, any overlap at all.