Remove the Fewest Overlapping Intervals

Problem Statement

You are given an array of intervals intervals where intervals[i] = [start_i, end_i]. Each interval represents a range on a 1D coordinate line.

Two intervals [a, b] and [c, d] (with a <= c) overlap if c < b. Intervals that touch at a single point (e.g., b == c) do not overlap.

Return the minimum number of intervals you must remove so that the remaining intervals are mutually non-overlapping.

Function Signature

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    pass

Constraints

• 1 <= len(intervals) <= 2 * 10^5
• intervals[i].length == 2
• -10^9 <= start_i < end_i <= 10^9
• The input may contain duplicate intervals (i.e., identical [start, end] pairs).

Examples

Example 1:

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Explanation: [1, 3] can be removed and the remaining intervals [[1, 2], [2, 3], [3, 4]] are non-overlapping.

Example 2:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2
Explanation: You need to remove two [1, 2] intervals so that the remaining [1, 2] has no duplicate overlaps.

Example 3:

Input: intervals = [[-50, -20], [-30, 10], [-20, 0], [0, 50]]
Output: 1
Explanation: Removing [-30, 10] leaves [[-50, -20], [-20, 0], [0, 50]], where touching endpoints (like -20 and 0) do not count as overlaps.

Edge Cases to Consider

• All intervals are mutually disjoint: output should be 0.
• All intervals are identical: output should be len(intervals) - 1.
• Completely nested intervals (e.g., [[1, 10], [2, 3]]): prioritize keeping the one with the earlier end time.