Non overlapping intervals#

Levels: level-4

Data structures: array

Algorithms: greedy

Patterns: intervals

Practice Link#

LeetCode

Description#

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

You may assume the interval’s end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Examples#

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

1Input: [[1,2],[1,2],[1,2]]
2Output: 2
3Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

1Input: [[1,2],[2,3]]
2Output: 0
3Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Python Solution#

 1class Solution(object):
 2    def eraseOverlapIntervals(self, intervals):
 3        """
 4        :type intervals: List[List[int]]
 5        :rtype: int
 6        """
 7        end = float('-inf')
 8        erased = 0
 9        for i in sorted(intervals, key=lambda i: i.end):
10            if i.start >= end:
11                end = i.end
12            else:
13                erased += 1
14        return erased