Non-overlapping Intervals

Merge Intervals

Problem

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

For example:

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.

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

Thought Process

• Sort the intervals by their start time. If two intervals overlap, the interval with larger end time will be removed so as to have as little impact on subsequent intervals as possible.

Solution

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        count = 0
        intervals = sorted(intervals) #sort on start time
        
        if not intervals:
            return 0
        
        currI = intervals[0]
        for i in range(1, len(intervals)):
            nextI = intervals[i]
            if nextI[0] < currI[1]:
                count+=1
                currI[1] = min(nextI[1], currI[1]) #erase the one with larger end time
            else:
                currI[1] = nextI[1] #upate end time

        return count
        
        
#Time: O(n)
#Space: O(1)