435. Non-overlapping Intervals

Description:

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.

 

 

'''
[1] sort and greedy)

-idea::
sort intervals(key is interval[0])
then, keep end point(interval[0])
while comparing next interval with end, It is advantageous to remove longer interval (greedy approach)

-code::
(below)

-T/C: O(nlogn)
-S/C: O(1)
'''
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # sort
        intervals.sort(key=lambda x:x[0])
        
        removed=0
        
        end=intervals[0][1]
        
        for i in range(1, len(intervals)):
            if end > intervals[i][0]:
                # update end, remove longer one
                end=min(end,intervals[i][1])
                removed+=1
            else:
                end=intervals[i][1]
        return removed