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.
Example 1: 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.
Example 2: Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
- code based on ending point
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key = lambda x: x[1])
last_end = intervals[0][1]
rm_count = 0
for i in range(1, len(intervals)):
if intervals[i][0] >= last_end:
last_end = intervals[i][1]
else:
rm_count += 1
return rm_count
- code, based on starting point
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort()
last_end = intervals[0][1]
rm_count = 0
for i in range(1, len(intervals)):
if intervals[i][0] >= last_end:
last_end = intervals[i][1]
else:
rm_count += 1
if intervals[i][1] <= last_end:
last_end = intervals[i][1]
return rm_count
The two intervals currently considered are overlapping and the end point of the later interval falls after the end point of the previous interval:In this case, we can work in a greedy manner and directly remove the later interval. To understand why this greedy approach works, we need to see the figure below, which includes all the subcases possible. It is clear from the figures that we choosing interval 1 always leads to a better solution in the future. Thus, the prevprev pointer remains unchanged and the count of intervals removed is incremented by 1.