Non-overlapping Intervals

Intuition

This mirrors the classic activity-selection idea. If we always hold onto the interval that ends the earliest, we leave the maximum amount of room for future intervals to fit without conflict. Sorting by end value lets us scan left to right and greedily accept an interval whenever its start is at or after the end of the last one we kept. Anything that starts too early to fit is counted as a deletion, and this locally optimal choice provably yields the globally minimal number of removals.

Algorithm walkthrough

1. 1Sort the intervals in ascending order of their end value.
2. 2Track the end of the most recently kept interval, starting at negative infinity.
3. 3For each interval, if its start is at least the tracked end, keep it and update the tracked end.
4. 4Otherwise it overlaps the kept interval, so increment the removal counter and leave the tracked end alone.
5. 5Return the removal counter once every interval has been processed.

Implementation

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