Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note: Intervals are non-overlapping even if they have a common point. For example, [1, 3] and [2, 4] are overlapping, but [1, 2] and [2, 3] are non-overlapping.

After [1,4] is removed, the rest of the intervals are non-overlapping.

Approach

Sort intervals by end time and greedily keep the interval that ends earliest. Whenever an interval overlaps the last kept interval, remove it (count it) instead of the earlier-ending one.

Why It Works

Keeping the interval with the smallest end time leaves the most room for future intervals. This greedy choice minimizes removals and yields a maximum set of non-overlapping intervals, so the number removed is minimal.

Complexity

• Time: O(n log n)
• Space: O(1)

Reference Implementation (Python)

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[1])
        removals = 0
        end = intervals[0][1]
        for start, finish in intervals[1:]:
            if start < end:
                removals += 1
            else:
                end = finish
        return removals