Non-overlapping Intervalsmedium

Non-overlapping Intervals

medium Coding Interview Patterns 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Find the minimum number of intervals to remove to eliminate all overlaps using greedy interval scheduling.

Related Skills

Task

Implement erase_overlap_intervals(intervals): sort intervals by finish time ascending. Greedily keep intervals that finish earliest to leave maximum room for future intervals.

Function Signature

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

Examples

Example 1: [[1,2],[2,3],[3,4],[1,3]]
Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Example 2: [[1,2],[1,2],[1,2]]
Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Constraints

1 <= len(intervals) <= 10^5
intervals[i].length == 2
-5 * 10^4 <= start_i < end_i <= 5 * 10^4

Python3Saved ✓

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

"""intervals: list of intervals [start, end].

Return the minimum number of intervals you need to remove to make the rest

of the intervals non-overlapping."""

# Your implementation here

pass

Case 1: [[1,2],[2,3],[3,4],[1,3]]

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]

Expected: 1

Case 2: [[1,2],[1,2],[1,2]]

Input: intervals = [[1, 2], [1, 2], [1, 2]]

Expected: 2