435. Non-overlapping Intervals

'''
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.
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.
'''
class Solution:
    def eraseOverlapIntervals(self, a: List[List[int]]) -> int:
        '''
        conditions: to remove overlapping ones
        remove the interval which ends late.
        Because we shall be greedy.
        '''
        a.sort(key=lambda x:(x[0],x[1]))
        n=len(a)
        cnt=0
        prev=[-inf,-inf]
        for i in range(n):
            if prev[1]<=a[i][0]:
                prev=a[i]
                continue
            else:
                cnt+=1
                if prev[1]>a[i][1]:
                    prev=a[i]
        return cnt