1288 Remove Covered Intervals

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        """
            main idea:determine condition: l<s and r < e. note the left,rightbound;  
        """
        cnt,l,r = 0,-1,-1
        intervals.sort(key = lambda t: t[0])
        for s, e in intervals:
            if e>r and s>l :
                cnt += 1
                l = s
            r = max(r,e)
        return cnt 

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        """
            main idea: sort by start in ascending order, and end by descending order; check if current e <= historical ending, cnt for interval to be removed + 1; return total interval - cnt

            time O(NlgN) space O(1)
        """
        # step1: initialize cnt 0 historical max right = 0, since interval dif must bigger than 1 ,so r = 0  is not possible 
        cnt,r = 0,0
        # step2: sort 
        intervals.sort(key = lambda t: (t[0],-t[1]))
        for s, e in intervals:
            # check if current end <= historical right 
            if e <= r :
                cnt += 1
            # why not just assign r = e? because high chance the latter e is smaller than historical right but start is bigger than current start point.Hence it may look like not crossed but actually does 
            # e.g. [[1,4],[1,2],[3,4]]
            r = e
        return len(intervals)- cnt

        ##########################################################
            def removeCoveredIntervals(self, A: List[List[int]]) -> int:
        """
        sort by start asc, diff of (end-start) desc
        define covered:  start >= prev_start  and end <= prev_end 
        """
        A.sort(key=lambda x: [x[0],-x[1]+x[0]])
        cnt = 0
        prev = None
        for s,e in A:
            if prev and prev[0] <= s and prev[1] >= e:
                cnt += 1
                continue# keep intervals with bigger 
            prev = (s,e)
        return len(A)-cnt