medium +20 pts

Non-overlapping Intervals

Find the minimum number of intervals to remove so the rest don't overlap.

You are given a list of intervals, where each interval is a list [start, end] with start < end. Two intervals are considered overlapping if they share any point in common (including endpoints). Your task is to find the minimum number of intervals you need to remove so that the remaining intervals are pairwise non-overlapping. Implement the function `erase_overlap_intervals(intervals)` that takes a list of intervals and returns an integer: the minimum number of intervals to remove. **Input:** A list of lists, each inner list has exactly two integers [start, end] with start < end. The list may be empty. **Output:** An integer. **Constraints:** - 0 <= len(intervals) <= 10^4 - -10^9 <= start < end <= 10^9 **Note:** You do not need to actually remove intervals; just compute the minimum number needed.

Constraints

0 <= len(intervals) <= 10^4; start < end for each interval.

Example

>>> erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]])
1
>>> erase_overlap_intervals([[1,2],[1,2],[1,2]])
2
>>> erase_overlap_intervals([[1,2],[2,3]])
0
>>> erase_overlap_intervals([])
0
20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort intervals by their end time. Greedily keep the interval that finishes earliest.
Track the end of the last kept interval. If the current interval starts before that end, it overlaps and must be removed.
Otherwise, keep the interval and update the end to the current interval's end.
The answer is the total number of intervals minus the number of kept intervals.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.