Non-overlapping Intervals — InterviewPrepKit

Solving tips

Reframe 'minimum removals' as n minus the maximum kept set: this is classic activity selection.
Sort by END time and greedily keep every interval whose start >= last kept end (counting the rest as removed); finishing earliest can never hurt the future (exchange argument).
Sorting by END is the key decision here, contrasting with merge/overlap problems that sort by start; a start-sorted greedy needs a fix and is error-prone.
Touching is allowed for these half-open intervals, so use '>=' not '>'; target O(n log n) time, O(1) space and avoid the O(n^2) LIS-style DP at n = 10^5.

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] and the rest are a clean chain.
intervals = [[1,2],[1,2],[1,2]] → 2 — three copies of the same interval; 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 not only exponential search but also the O(n^2) DP — the intended solution is O(n log n) greedy.

Think about it first

Hint 1

"Minimum removals" is the same number as n minus the maximum number of intervals you can keep. Maximizing the kept set is the classic activity-selection question.

Hint 2

Suppose you must keep some interval as the first one in your non-overlapping set. Between two candidates that both fit, why is the one that ends earlier never a worse choice?

Hint 3

Sort by end time. Sweep left to right keeping a running "last kept end": keep an interval if its start is ≥ that value (and update it), otherwise count it as removed. Ending earliest leaves maximal room for the future — that exchange argument is the whole proof.

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

class Solution:
    def eraseOverlapIntervals(self, 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 doesn’t tame it directly — and with n = 10^5, exponential is dead on arrival.

Approach 2 — DP: longest non-overlapping subsequence

The insight: removals are minimized exactly when the kept set is maximized, and “maximum set of mutually non-overlapping intervals” has optimal substructure just 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

class Solution:
    def eraseOverlapIntervals(self, 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]].

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

Complexity: O(n^2) time, O(n) space. Correct, but n = 10^5 means ~10^10 pair checks — the constraints kill this one too. It’s worth knowing because it generalizes (e.g., to weighted interval scheduling, where greedy fails).

Approach 3 — Greedy by earliest end (activity selection)

The insight: 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 classic exchange argument). So sort by end and greedily keep everything compatible.

from typing import List

class Solution:
    def eraseOverlapIntervals(self, 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,2]: 1 >= -inf → keep, last_end = 2.
[2,3]: 2 >= 2 → keep (touching is fine), last_end = 3.
[1,3]: 1 >= 3 is false → remove, removed = 1.
[3,4]: 3 >= 3 → keep, last_end = 4.
Answer 1. Matches the example — and note the greedy removed exactly the interval the explanation 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) — read what the problem asks for.
Reaching for the O(n^2) DP under these constraints — it times out at n = 10^5; save it for 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 can never hurt the future. Contrast with merge/overlap questions, which sort by start. Which endpoint you sort on is the first decision of every intervals problem, and this problem is the canonical reason end-sorting exists.