Non-overlapping Intervals

Problem

You are given a list of intervals [start, end). Remove as few intervals as possible so that the remaining intervals are pairwise non-overlapping, and return that minimum number of removals.

Intervals that only touch do not overlap: [1,2) and [2,3) can coexist. Duplicated intervals are allowed in the input, and duplicates of the same interval do overlap each other.

Examples

• intervals = [[1,2],[2,3],[3,4],[1,3]] → 1 — remove [1,3]; the remaining intervals are non-overlapping.
• intervals = [[1,2],[1,2],[1,2]] → 2 — three copies of the same interval, so only one can stay.
• intervals = [[1,2],[2,3]] → 0 — touching at 2 is fine, nothing to remove.

Constraints

• 1 <= len(intervals) <= 10^5
• -5 * 10^4 <= start < end <= 5 * 10^4

n = 10^5 rules out both exponential search and the O(n^2) DP. The intended solution is an O(n log n) greedy.

Think about it first

TL;DR

Greedy: sort by end time, keep every interval that starts after the last kept end — O(n log n) time, O(1) extra space.

Approach 1 — Brute force: try keeping or removing each interval

For every interval, branch on “remove it” (cost 1) versus “keep it” (cost 0, but it constrains what can follow). Sorting by start first lets each branch carry just one piece of state: the end of the last kept interval.

from typing import List

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda it: it[0])
    n = len(intervals)

    def best(i: int, last_end: int) -> int:
        if i == n:
            return 0
        # Option A: remove interval i.
        removed = 1 + best(i + 1, last_end)
        # Option B: keep it, if it fits.
        if intervals[i][0] >= last_end:
            kept = best(i + 1, intervals[i][1])
            return min(removed, kept)
        return removed

    return best(0, float("-inf"))

Complexity: O(2^n) time, O(n) recursion depth. last_end is not a small state (it can be any coordinate), so plain memoization does not reduce it directly, and at n = 10^5 an exponential search is infeasible.

Approach 2 — DP: longest non-overlapping subsequence

Removals are minimized exactly when the kept set is maximized, and the maximum set of mutually non-overlapping intervals has optimal substructure, like Longest Increasing Subsequence. Sort by start; let dp[i] be the size of the largest non-overlapping set whose last interval is i; extend from any earlier j that ends by the time i starts.

from typing import List

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda it: it[0])
    n = len(intervals)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if intervals[j][1] <= intervals[i][0]:
                dp[i] = max(dp[i], dp[j] + 1)
    return n - max(dp)

Walkthrough on [[1,2],[2,3],[3,4],[1,3]]: sorted by start → [[1,2],[1,3],[2,3],[3,4]].

1. dp[0] = 1 for [1,2].
2. [1,3]: no earlier interval ends by 1 → dp[1] = 1.
3. [2,3]: [1,2] ends at 2 <= 2 → dp[2] = 2.
4. [3,4]: [1,3] and [2,3] both end by 3 → dp[3] = dp[2] + 1 = 3.
5. Keep max(dp) = 3 intervals, so remove 4 - 3 = 1. Matches the example.

Complexity: O(n^2) time, O(n) space. Correct, but at n = 10^5 it performs roughly 10^10 pair checks and times out. It is still worth knowing because it generalizes to weighted interval scheduling, where the greedy fails.

Approach 3 — Greedy by earliest end (activity selection)

Among all intervals you could keep next, the one that ends earliest is always a safe choice: swapping it in place of any other candidate can only leave more room for later intervals (a standard exchange argument). So sort by end and greedily keep everything compatible.

from typing import List

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda it: it[1])
    removed = 0
    last_end = float("-inf")
    for start, end in intervals:
        if start >= last_end:
            last_end = end       # keep it
        else:
            removed += 1         # overlaps the kept set
    return removed

Walkthrough on [[1,2],[2,3],[3,4],[1,3]]: sorted by end → [[1,2],[2,3],[1,3],[3,4]].

1. [1,2]: 1 >= -inf → keep, last_end = 2.
2. [2,3]: 2 >= 2 → keep (touching is fine), last_end = 3.
3. [1,3]: 1 >= 3 is false → remove, removed = 1.
4. [3,4]: 3 >= 3 → keep, last_end = 4.
5. Answer 1, matching the example. The greedy removed the same interval the problem statement named.

Complexity: O(n log n) time for the sort, O(1) extra space.

Common pitfalls

• Sorting by start and greedily keeping the first compatible interval — a long early interval like [1,100] then blocks everything; the greedy is only correct sorted by end. (A start-sorted greedy can be repaired by always discarding the larger end on conflict, but end-sorted is the cleaner statement.)
• Using start > last_end instead of >= — that counts touching intervals like [1,2] and [2,3] as conflicts and over-removes.
• Returning the size of the kept set instead of n - kept (or vice versa) — the problem asks for the number of removals.
• Reaching for the O(n^2) DP under these constraints — it times out at n = 10^5. It only pays off in the weighted variant.

Pattern takeaway

When the question is “keep the most / remove the fewest intervals,” sort by end time and greedily commit to the earliest-ending compatible interval; finishing early never hurts later choices. Contrast with merge/overlap questions, which sort by start. Which endpoint you sort on is the first decision in any intervals problem.