435. Non-overlapping Intervals (Python)

Related Topic

Greedy.

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.

Sample I/O

Example 1

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

Example 2

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

Example 3

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

Constraints:

• 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.

Methodology

We can use greedy to solve the question. You can use similar method of question 452. Minimum Number of Arrows to Burst Balloons to solve this question. We sort the given input list by end value of each element. We set a left boundary and Now we only need to compare the current start and previous end. If the current start is greater or equal than previous end. Then there is no overlaping we update the left boundary to the current end and continue iteration. Otherwise the is overlaping then we need to increase 1 to the number of remove.

def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        size = len(intervals)
        if size<=1: return 0
        intervals.sort(key=lambda x: x[1])
        first_end = intervals[0][1]
        res = 0
        for i in range(1,size):
            start, end = intervals[i]
            if start>=first_end:
                first_end=end
            else:
                res+=1
        return res

BigO

Time complexity : O(nlogn) due to sorting the list where n is the size of input.