Remove Overlapping Intervals
Intermediate
intervals[i] = [start, end]. Return the fewest intervals to remove so that the rest do not overlap. Intervals that only touch (one ends where the next starts) do not overlap.
For [[1, 2], [2, 3], [3, 4], [1, 3]] the answer is 1 (remove [1, 3]).
The starter code builds the longest chain with a double loop. It is correct but too slow for many intervals.
Examples
Example 1
Input:
erase_overlap([[1, 2], [2, 3], [3, 4], [1, 3]])
Output:
1
Example 2
Input:
erase_overlap([[1, 2], [1, 2], [1, 2]])
Output:
2
Constraints
0 <= len(intervals) <= 2000000 <= start < end <= 10**9
Theory
Go to TheoryKeywords
dsa-sheetgreedygreedy-basics
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.