Non-overlapping Intervals — LeetCode 435 Python Solution

The problem

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. Note that intervals which only touch at a point are non-overlapping.

Example

Input

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

Output

1

Explanation

[1,3] can be removed and the rest of the intervals are non-overlapping.

Python solution

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = len(intervals)
        pre = -inf
        for l, r in intervals:
            if pre <= l:
                ans -= 1
                pre = r
        return ans

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 435. Non-overlapping Intervals is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems