Non Overlapping Intervals

Removing the fewest intervals to leave a non-overlapping set is the same as keeping the largest possible non-overlapping subset. Sort by start, then for every interval compute the longest chain of non-overlapping intervals that can follow it (classic “longest increasing subsequence”-style DP): dp[i] = 1 + max(dp[j]) over every j that starts at or after intervals[i] ends. The answer is n minus the best chain length.

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

The nested loop compares every pair of intervals — O(n²) time, O(n) space for the dp array. Correct, but it recomputes overlap relationships that a single greedy pass can settle in one look-ahead.

Sort intervals by their end time. Greedily keep an interval whenever it starts at or after the end of the last interval kept — keeping the interval that finishes earliest always leaves the most room for future intervals, so this greedy choice never costs an optimal solution. Every interval that cannot be kept must be removed.

class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort(key=lambda iv: iv[1])
        removals = 0
        prev_end = float('-inf')
        for start, end in intervals:
            if start >= prev_end:
                prev_end = end
            else:
                removals += 1
        return removals

Watch the dashed prev_end gate sweep right: an interval is kept only when its bar reaches the line, and every removal is a bar that starts behind it.

Why sorting by end (not start) matters: the interval that ends earliest always leaves the most room for everything after it, so it is always safe to keep. Complexity: dominated by the sort → O(n log n) time; only a running counter and prev_end are tracked → O(1) extra space.