LC435 Non-overlapping Intervals

class Solution:
    def eraseOverlapIntervals(self, A: List[List[int]]) -> int:
        """  tc O(NlgN)  sc O(1)
        greedy,get earliest end time as possible to spare more space to get more potential non-overlaps   
        1. sort by end
        2. loop intervals, check if current start >= prev end time. if yes, update previous valid end time with current end time; otherwise increase cnt by one to mark current interval need to be removed 
        3. return cnt 
        """
        if not A:return 0
        A.sort(key = lambda x:x[1])
        cnt,pre_end = 0,float('-inf')
        for s,e in A:
            # max non-overlap holds 
            if pre_end <= s:
                pre_end = e
            else:
                cnt += 1 
        return cnt