Given a list of intervals, remove all intervals that are covered by another interval in the list.
Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d.
After doing so, return the number of remaining intervals.
 
Example 1:
Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

Example 2:
Input: intervals = [[1,4],[2,3]]
Output: 1

Example 3:
Input: intervals = [[0,10],[5,12]]
Output: 2

Example 4:
Input: intervals = [[3,10],[4,10],[5,11]]
Output: 2

Example 5:
Input: intervals = [[1,2],[1,4],[3,4]]
Output: 1

 
Constraints:

1 <= intervals.length <= 1000
intervals[i].length == 2
0 <= intervals[i][0] < intervals[i][1] <= 10^5
All the intervals are unique.

Difficulty: interview

Starter code:

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], -x[1]))
        
        prev_end = result = 0
        for _, end in intervals:
            if end > prev_end:
                result += 1; prev_end = end
                
        return result

class Solution:
    def removeCoveredIntervals(self, l: List[List[int]]) -> int:
        l.sort(reverse=True,key=lambda x:(x[1],-x[0]))
        n=len(l)
        c=n
        for i in range(n-1):
            if(l[i][0]<=l[i+1][0] and l[i][1]>=l[i+1][1]):
                l[i+1]=l[i]
                c-=1
        return c

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        from functools import cmp_to_key
        
        def cmp(a,b):
            if a[0]>b[0]:
                return 1
            if a[0]<b[0]:
                return -1
            if a[1]>b[1]:
                return -1
            return 1
            
        lis=[]
        if len(intervals)==1:
            return 1
        for x,y in intervals:
            lis.append((x,y))
        lis.sort(key = cmp_to_key(cmp))
        fin=[]
        fin.append(list(lis[0]))
        for i in range(1,len(lis)):
            currx,curry=lis[i]
            flag=0
            for j in range(len(fin)):
                if curry<=fin[j][1] and currx>=fin[j][0]:
                    flag=1
            if flag==0:
                fin.append([currx,curry])
        return len(fin)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], -x[1]))
        
        covering = 0
        used = set()
        for i, (si, ei) in enumerate(intervals):
            for sj, ej in intervals[i+1:]:                
                if sj > ei:
                    break
                if ej > ei:
                    continue
                if (sj, ej) in used:
                    continue
                used.add((sj, ej))
                covering += 1
                
        return len(intervals) - covering
            


class Tree:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __lt__(self, other):
        if self.val[0] < other.val[0]: return True
        elif self.val[0] > other.val[0]: return False
        else:
            if self.val[1] > other.val[1]: return True
            else: return False

    def __le__(self, other):
        return self < other or self.val == other.val

    def __gt__(self, other): return not self <= other

    def __ge__(self, other): return not self < other

    def __eq__(self, other): return self <= other and self >= geother

    def __neq__(self, other): return not self == other

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        tree = Tree(val=tuple(intervals[0]))
        for x, y in intervals[1:]:
            this = Tree((x, y))
            cursor = tree
            while True:
                if this < cursor:
                    if cursor.left:
                        cursor = cursor.left
                    else:
                        cursor.left = this
                        break
                elif this > cursor:
                    if cursor.right:
                        cursor = cursor.right
                    else:
                        cursor.right = this
                        break
                else:
                    break

        buff = [tree]
        count, last = 0, None
        while buff:
            while buff[-1].left: buff.append(buff[-1].left)
            while buff and not buff[-1].right:
                this = buff.pop(-1)
                if count == 0: count, last = 1, this.val[1]

                else:
                    if this.val[1] > last: count, last = count + 1, this.val[1]

            if buff:
                this = buff.pop(-1)
                if count == 0: count, last = 1, this.val[1]

                else:
                    if this.val[1] > last: count, last = count + 1, this.val[1]

                buff.append(this.right)

        return count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        
        
        for i in range(0,len(intervals)-1):
            minel=intervals[i]
            minid=i
            for j in range(i+1,len(intervals)):
                evl=intervals[j]
                
                if evl[0]<minel[0]:
                    
                    minel=evl
                    minid=j
            intervals[i],intervals[minid]=intervals[minid],intervals[i]
        #print(intervals)
        
        
        
        
        c=0
        prevl=intervals[0][0]
        prevh=intervals[0][1]
        
        for x in range(1,len(intervals)):
            
            
            curl=intervals[x][0]
            curh=intervals[x][1]
            if curh<=prevh:
                c=c+1
                continue
            if curl==prevl:
                
                c=c+1
                if curh>prevh:
                    prevh=curh
                continue
            prevl=curl
            prevh=curh
        return len(intervals)-c
            
            
        
        #return 1    
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        # sort based on [smallest start time, largest end time): O(n*log(n))
        # Sliding window upto the next start that is larger than current end
        # If they overlap then discard.
        
        ordered_intervals = sorted(intervals, key=lambda x: (x[0],-x[1]))
        candidates = set()
        for i in range(len(intervals)):
            
            curr_start, curr_end = ordered_intervals[i]
            
            for j in range(i+1, len(intervals)):
            
                next_start, next_end = ordered_intervals[j]
                if next_start >= curr_end:
                    break
                    
                if next_end <= curr_end:
                    candidates.add(j)
                    
        #result = []
        #for i, interval in enumerate(ordered_intervals):
        #    if i not in candidates:
        #        result.append(interval)
        return len(intervals) - len(candidates)
                
                


import numpy as np
class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        copy_intervals = intervals[:]
        for i, interval_1 in enumerate(copy_intervals):
            for interval_2 in copy_intervals[i+1:]:
                if interval_1[0] >= interval_2[0] and interval_1[1] <= interval_2[1]:
                    if interval_1 in intervals:
                        intervals.remove(interval_1)
                    break
                if interval_1[0] <= interval_2[0] and interval_1[1] >= interval_2[1]:
                    if interval_2 in intervals:
                        intervals.remove(interval_2)
        return len(intervals)

class Solution:
    def removeCoveredIntervals(self, arr: List[List[int]]) -> int:
        arr.sort(reverse=True)
        ans=0
        n=len(arr)
        take=[1]*n
        for i in range(n-1):
            for j in range(i+1,n):
                if arr[i][0]>=arr[j][0] and arr[i][1]<=arr[j][1]:
                    take[i]=0
                    break
        # print(arr)
        # print(take)
        for i in range(n-1,-1,-1):
            for j in range(i-1,-1,-1):
                if arr[i][0]>=arr[j][0] and arr[i][1]<=arr[j][1]:
                    take[i]=0
                    break
        # print(arr)
        # print(take)
        return take.count(1)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda interval: (interval[0], -interval[1]))
        length = len(intervals)
        start = 0
        removed = 0
        
        while start < length-1 :
            curr = start + 1
            while curr < length:
                if intervals[curr][0] != -1:
                    if (intervals[curr])[0] >= (intervals[start])[0] and (intervals[curr])[1] <= (intervals[start])[1]:
                        removed+=1
                        (intervals[curr])[0] = -1
                        (intervals[curr])[1] = -1
                curr+=1
            start+=1
        return length - removed


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals=sorted(intervals,key=lambda x:x[1])
        n=len(intervals)
        cnt=0
        for i in intervals:
            for j in intervals:
                if j==i:
                    continue
                if i[1]<=j[1] and i[0]>=j[0]:
                    cnt+=1
                    break
        return(n-cnt)
                    
        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
         # n log n time
        intervals.sort(reverse = True)
        intervals.sort(key = lambda i: i[1])
        
        covered = set() # n space
        
        for i, (c, d) in enumerate(intervals):
            for (a, b) in intervals[0: i]:
                #print((a,b), (c,d), c <= a, b <= d)
                
                if  c <= a and b <= d:
                    #print(\"covered\")
                    covered.add((a, b))
                    
        #print(covered)
        return len(intervals) - len(covered)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        def overlap(interval1, interval2):
            if interval1[0] > interval2[0]:
                interval1, interval2 = interval2, interval1
            return interval1[1] >= interval2[1]
        
        intervals.sort(key = lambda x: (x[0], -x[1]))
        print(intervals)
        
        count = 0

        res = [intervals[0]]
        for i in intervals[1:]:
            print((i, res[-1]))
            if not overlap(res[-1], i):
                res.append(i)

        return len(res)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
         # n log n time
        intervals.sort(reverse = True)
        intervals.sort(key = lambda i: i[1])
        
        covered = set() # n space
        
        for i, (c, d) in enumerate(intervals):
            for (a, b) in intervals[0: i]:           
                #print((a,b), (c,d), c <= a, b <= d)
                
                if  c <= a and b <= d:
                    #print(\"covered\")
                    covered.add((a, b))
                    
        #print(covered)
        return len(intervals) - len(covered)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        flag = [0]*n
        i = 0
        
        while i<n:
            j = i+1
            while j<n:
                if flag[i]!=1:
                    print((i,j,intervals[i], intervals[j]))
                    if intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]:
                        flag[i] = 1
                    if intervals[i][0] <= intervals[j][0] and intervals[j][1] <= intervals[i][1]:
                        flag[j] = 1
                j+=1  
            i+=1                
                

        return flag.count(0)
            


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        new = sorted(intervals, key = lambda x : x[1]-x[0] , reverse = True)
        ans = []
        for i,v in enumerate(new):
            flag = False
            for elem in new[:i]:
                if v[0] >= elem[0] and v[1] <= elem[1]:
                    flag = True
            if flag == False:
                ans.append(v)
        return len(ans)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        removed = 0
        removedSet = set()
        for ind1 in range(len(intervals)):
            for ind2 in range(len(intervals)):
                if ind1 == ind2 or ind1 in removedSet: continue
                interval1 = intervals[ind1]
                interval2 = intervals[ind2]
                
                if interval1[0] >= interval2[0] and interval1[1] <= interval2[1]:
                    removed += 1
                    removedSet.add(ind1)
                        
        return len(intervals) - removed


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        flag = [True for i in range(n)]
        ctr = n
        for i in range(n):
            for j in range(n):
                if i!=j and flag[i] and flag[j]:
                    a,b = intervals[i]
                    c,d = intervals[j]
                    if(c<=a and b<=d):
                        flag[i] = False
                        ctr-=1
                    elif(a<=c and d<=b):
                        flag[j] = False
                        ctr-=1
        return ctr

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        def covered(a, b):
            # True if a is covered by b
            
            return a[0] >= b[0] and a[1] <= b[1]
        
        deleted = set()
        
        for i in range(len(intervals)):
            for j in range(len(intervals)):
                
                if i!=j and i not in deleted:
                    if covered(intervals[i], intervals[j]):
                        # print(i, j)
                        deleted.add(i)
        
        return len(intervals) - len(deleted)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        int_set = set(tuple(i) for i in intervals)
        for i, (a, b) in enumerate(intervals):
            for c, d in intervals[i+1:]:
                if a <= c and d <= b and (c, d) in int_set:
                    int_set.remove((c, d))
                elif c <= a and b <= d and (a, b) in int_set:
                    int_set.remove((a, b))
        return len(int_set)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        covered=0
        m = {}
        for [l,r] in intervals:
            if l not in m:
                m[l] = r
            else:
                m[l] = max(r, m[l])
                covered +=1
        
        a = []
        for i in m:
            a.append([i,m[i]])
        
            
        a.sort(key=lambda x: x[0])
        # print(a)
        _c = set()
        for i in range(len(a)):
            for j in range(i+1,len(a)):
                if a[j][1] <= a[i][1] and j not in _c:
                    _c.add(j)
                    covered += 1

        return len(intervals) - covered


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda tup: tup[1] - tup[0], reverse = True)
        covered = set()
        
        for i in range(len(intervals)):
            s, e = intervals[i]
            for j in range(i + 1, len(intervals)):
                s2, e2 = intervals[j]

                if s <= s2 and e2 <= e:
                    covered.add(j)
                    
                
        return len(intervals) - len(covered)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        l = len(intervals)
        a = [True] * l
        
        for i in range(l):
            for j in range(l):
                if i == j:
                    continue
                
                if not a[i] or not a[j]:
                    continue
                    
                if intervals[i][0] <= intervals[j][0] and intervals[i][1] >= intervals[j][1]:
                    a[j] = False
                    
        return a.count(True)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        intervals.sort(key=lambda x: (x[0], -x[1]))
        ans = len(intervals)
        i = 0
        while i < len(intervals):
            for j in range(i):
                if intervals[j][0] <= intervals[i][0] and intervals[j][1] >= intervals[i][1]:
                    ans -= 1
                    break
            i += 1
        return ans
                


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key=lambda k: (k[0], -k[1]))
        removed = set()
        i = 0
        while i < len(intervals) - 1:
            for j in range(i + 1, len(intervals)):
                if intervals[j][1] <= intervals[i][1] and j not in removed:
                    removed.add(j)
            i += 1
        return len(intervals) - len(removed)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
         # n log n time
        intervals.sort(reverse = True)
        intervals.sort(key = lambda i: i[1])
        
        covered = set() # n space
        
        for i, (c, d) in enumerate(intervals):
            for (a, b) in intervals[0: i]:
                if b < c:
                    continue
                    
                #print((a,b), (c,d), c <= a, b <= d)
                
                if  c <= a and b <= d:
                    #print(\"covered\")
                    covered.add((a, b))
                    
        #print(covered)
        return len(intervals) - len(covered)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        intervals.sort(key=lambda x: (x[0], -x[1]))
        removeSet = set()
        
        for i in range(n):
            interval1 = intervals[i]
            
            for j in range(i + 1, n):
                interval2 = intervals[j]
                if interval2[0] >= interval1[1]: break
                    
                if interval2[1] <= interval1[1]:
                    removeSet.add(j)
                    
        return n - len(removeSet)
            
        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        l = len(intervals)
        removed = set()
        intervals.sort(key = lambda i: (i[0], -i[1]))
        for i in range(l):
            for j in range(i + 1, l):
                if intervals[i][1] >= intervals[j][1]:
                    removed.add(j)
        return l - len(removed)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        discarded = [False] * len(intervals)
        for i in range(len(intervals)):
            for j in range(len(intervals)):
                if i == j:
                    continue
                if discarded[j]:
                    continue
                if intervals[j][0] >= intervals[i][0] and intervals[j][1] <= intervals[i][1]:
                    discarded[j] = True
        kount = 0
        for i in range(len(intervals)):
            if not discarded[i]:
                kount = kount + 1
        return kount
                
                    
            


def checkCovered(a, b):
    if a[0] < b[0] or a[1] > b[1]:
        return False
    
    return True

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        covered = [0] * len(intervals)
        for i in range(len(intervals) - 1):
            a = intervals[i]
            for j in range(i+1, len(intervals)):
                b = intervals[j]

                if covered[i] == 0:
                    if checkCovered(a, b):
                        covered[i] = 1

                if covered[j] == 0:
                    if checkCovered(b, a):
                        covered[j] = 1

        return covered.count(0)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        i=0
        j=1
        while i<len(intervals) and j<len(intervals):
            if intervals[i][0]>=intervals[j][0] and intervals[i][1]<=intervals[j][1]:
                #print('%d:[%d, %d]'%(i,intervals[i][0],intervals[i][1]))
                #print('%d:[%d, %d]'%(j,intervals[j][0],intervals[j][1]))
                #print('----------------')
                
                intervals.pop(i)
                i,j=0,1
            elif intervals[i][0]<=intervals[j][0] and intervals[i][1]>=intervals[j][1]:
                #print('%d:[%d, %d]'%(j,intervals[j][0],intervals[j][1]))
                #print('%d:[%d, %d]'%(i,intervals[i][0],intervals[i][1]))
                #print('----------------')
                intervals.pop(j)
                i,j=0,1            
            else:
                j+=1
            
            if j==len(intervals):
                i+=1
                j=i+1
        
        return len(intervals)

class Solution:
    
    def isCovered(self, A, B):
        if(A[0] <= B[0] and A[1]>= B[1]):
            return True
        
        return False
    
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        index = 0
        while(index < len(intervals)):
            delete = False
            i = intervals[index]
            for j in intervals:
                if(intervals[index] == j):
                    continue
                    
                if(self.isCovered(i,j)):
                    intervals.remove(j)
                    index = -1
                    break
                if(self.isCovered(j,i)):
                    intervals.remove(i)
                    index = -1
                    break
                    
            index += 1
        
        return len(intervals)


import numpy as np
class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        current_intervals = np.array(intervals)
        
        for interval in intervals:
            mask = np.logical_and(current_intervals[:, 0] >= interval[0], current_intervals[:, 1] <= interval[1] )
            current_intervals = current_intervals[np.logical_not(mask)]
            if sum(mask):
                current_intervals = np.append(current_intervals, [interval], axis=0)
            
        return len(current_intervals)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        seen = set()
        n = len(intervals)
        for i in range(n):
            for j in range(n):
                if j == i or j in seen:
                    continue
                st1, ed1 = intervals[i][0], intervals[i][1]
                st2, ed2 = intervals[j][0], intervals[j][1]
                
                if st1 <= st2 and ed2 <= ed1:
                    seen.add(j)
                #print(st1,ed1, st2, ed2, seen)
        return n-len(seen)

class Solution:
    
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        results = []
        max_end = float('-inf')
        for i in intervals:
            if i[1] > max_end:
                max_end = i[1]
                if len(results) == 0 or i[0] != results[-1][0]:
                    results.append(i)
                else:
                    results[-1] = i         
            print(results)
        return len(results)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        I = len(intervals)
        count = 0
        covered = {}
        removed = {}
        for i in range (0, I):
            for j in range(0, I):
                if i == j:
                    continue
                if j in removed or i in removed:
                    continue
                if intervals[i][0] <= intervals[j][0] and intervals[i][1] >= intervals[j][1]:
                    if (i, j) not in covered and (j, i) not in covered:                    
                        count += 1
                        covered[(i, j)] = 1
                        covered[(j, i)] = 1
                        removed[j] = j
        return len(intervals) - count            


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        deleted = set()
        for i in range(len(intervals)):
            for j in range(len(intervals)):
                if i != j and j not in deleted and intervals[i][0] <= intervals[j][0] < intervals[j][1] <= intervals[i][1]:
                    deleted.add(j)
        return len(intervals) - len(deleted)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) < 2:
            return len(intervals)
        intervals.sort(key=lambda interval: interval[0])
        start, idx = 0, 1
        removed = set()

        while start < len(intervals):
            if idx == len(intervals):
                start += 1
                idx = start + 1
                continue
            if idx in removed:
                idx += 1
                continue
            if intervals[start][1] < intervals[idx][0]:
                start += 1
                idx = start + 1
                continue
            if intervals[start][1] >= intervals[idx][1]:
                removed.add(idx)
                idx += 1
                continue
            if intervals[start][1] <= intervals[idx][1]:
                if intervals[start][0] == intervals[idx][0]:
                    removed.add(start)
                    start = idx
                idx += 1
        return len(intervals) - len(removed)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        covered = set()
        for i in range(len(intervals) - 1):
            a1, b1 = intervals[i]
            for j in range(i + 1, len(intervals)):
                a2, b2 = intervals[j]
                #print('Interals: [{},{}) vs [{},{})'.format(
                #     a1, b1, a2, b2))
                if a2 <= a1 and b1 <= b2:
                    #print('covered: {} by {}'.format(i, j))
                    covered.add(i)
                elif a1 <= a2 and b2 <= b1:
                    #print('covered: {} by {}'.format(j, i))
                    covered.add(j)
        return len(intervals) - len(covered)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        N = len(intervals)
        intervals.sort(key=lambda x: x[0])
        count = 0
        covered = set()
        for i in range(N):
            for j in range(N):
                if i!= j and j not in covered:
                    min_x = min(intervals[i][0], intervals[j][0])
                    max_y = max(intervals[i][1], intervals[j][1])
                    if intervals[i] == [min_x,max_y]:
                        covered.add(j)
                        count += 1

        return N-count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        lis = intervals
        # print(\".\")
        # i = 0
        arr = []
        # print(lis)
        lis.sort()
        # print(lis)
        # count = 0
        for i in range(0,len(lis)):
            # temp = lis.copy()
            # print(lis)
            if lis[i] in arr:
                continue
            for j in range(i+1,len(lis)):
                if i<len(lis) and j<len(lis):
                    # print(\".\")
                    if (lis[i][0]>=lis[j][0] and lis[i][1]<=lis[j][1] and lis[i] not in arr): 
                        # print(\"if\",lis[i],lis[j])
                        arr.append(lis[i])
                        # lis.remove(lis[i])
                    if (lis[i][0]<=lis[j][0] and lis[i][1]>=lis[j][1] and lis[j] not in arr):
                        # print(\"elif \",lis[j],lis[i])
                        arr.append(lis[j])
                        # lis.remove(lis[j])
                    # else:
                        # i = i + 1 
                else:
                    break
            # lis = temp.copy()
        return len(lis) - len(arr)
#         Input: intervals = [[1,4],[3,6],[2,8]]
# Output: 2


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n=len(intervals)
        for i in range(n):
            for j in range(i+1,n):
                if intervals[i][0]>intervals[j][0]:
                    intervals[i],intervals[j]=intervals[j],intervals[i]
        l=[intervals[0]]
        for i in range(1,n):
            if (intervals[i][0]>=l[-1][0] and intervals[i][1]<=l[-1][1]):
                intervals[i]=-1
            elif(intervals[i][0]<=l[-1][0] and intervals[i][1]>=l[-1][1]):
                intervals[i-1]=-1
            if intervals[i]!=-1:
                l.append(intervals[i])
        print(intervals)
        return n-intervals.count(-1)


from functools import cmp_to_key
class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        def cmp_intervals(left, right):
            if left[0] == right[0]:
                return right[1] - left[1]
            return left[0] - right[0]
        
        n = len(intervals)
        s_intervals = sorted(intervals, key = cmp_to_key(cmp_intervals))
        covered = set()
        
        for i in range(n - 1):
            a, b = s_intervals[i]
            
            for j in range(i + 1, n):
                c, d = s_intervals[j]
                
                if a <= c and d <= b:
                    covered.add((c, d))
                    
        return n - len(covered)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        
        drop = set([])
        for i in range(len(intervals)):
            x, y = intervals[i]
            for j in range(i+1, len(intervals)):
                a, b = intervals[j]
                
                if x >= a and y <= b:
                    drop.add(i)
                    break
                elif a >= x and b <= y:
                    drop.add(j)
                    
        return len(intervals)-len(drop)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        intervals.sort(reverse=True)
        temp = []
        for i in range(n-1, -1, -1):
            for k in range(0, n):
                if (i!=k) and (intervals[k][0]<=intervals[i][0] and intervals[i][1]<=intervals[k][1]):
                    temp.append(intervals[i])
                    break
        
        res = [i for i in intervals if i not in temp]
        return len(res)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda t: [t[0], t[1]])
        deleted = set()
        i=0
        while i < len(intervals):
            boundary = tuple(intervals[i])
            if not boundary in deleted:
                j = i + 1
                stop = False
                while not stop and j < len(intervals):
                    comparedBoundary = tuple(intervals[j])
                    if comparedBoundary[0] == boundary[0]:
                        deleted.add(boundary)
                        stop = True
                        
                    elif comparedBoundary[0] >= boundary[1]:
                        stop = True
                    elif comparedBoundary[1] <= boundary[1]:
                        deleted.add(comparedBoundary)
                    j+=1
            i+=1
                
        return len(intervals) - len(deleted)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        for i in range(len(intervals)):
            for j in range(i, len(intervals)):
                if i == j or type(intervals[i][0]) == str or type(intervals[j][0]) == str:
                    continue
                elif intervals[i][0] >= intervals[j][0] and intervals[i][1] <= intervals[j][1]:
                    intervals[i] = ['', '']
                elif intervals[j][0] >= intervals[i][0] and intervals[j][1] <= intervals[i][1]:
                    intervals[j] = ['', '']
        interval = []
        for ele in intervals:
            if ele != ['', '']:
                interval.append(ele)
        return len(interval)


from collections import defaultdict
class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n=len(intervals)
        m=n
        visited=defaultdict(lambda:False)
        for i in range(n):
            for j in range(n):
                if i==j or visited[j]:
                    continue
                if intervals[i][0]<=intervals[j][0]:
                    if intervals[i][1]>=intervals[j][1]:
                        visited[j]=True
                        m-=1
        return m

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        removed = [False] * n
        intervals = sorted(intervals, key= lambda interval: (interval[0], -interval[1]))
        # print(intervals)
        for i in range(len(intervals)):
            start, end = intervals[i]
            j = i + 1
            while j < len(intervals) and end >= intervals[j][0]:
                # print(intervals[i], intervals[j])
                if end >= intervals[j][1] and not removed[j]:
                    removed[j] = True
                    n -= 1
                j += 1
                
        return n

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n=len(intervals)
        flags=[]
        for i in range(n):
            flags.append(0)
        k=n
        for i in range(n):
            for j in range(n):
                if(i==j or flags[j]==1):
                    continue
                if(intervals[i][0]<=intervals[j][0] and intervals[i][1]>=intervals[j][1]):
                    flags[j]=1
                    k-=1
        return k
                    
        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        L = len(intervals)
        discard = set()
        for i in range(L):
            x, y = intervals[i]
            for j in range(i+1, L):
                a, b = intervals[j]
                if a <= x and b >= y:
                    discard.add((x, y))
                elif x <= a and y >= b:
                    discard.add((a, b))
        return L - len(discard)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        length = len(intervals)
        if length <= 1:
            return length
        
        temp = intervals[:]
        
        i, j = 0, 1
        
        while i < len(intervals) - 1:
            j = i + 1
            while j < len(intervals):
                if self.ainbHelper(intervals[i], intervals[j]) == True:
                    try: 
                        temp.remove(intervals[i])
                    except:
                        pass
                    break
                elif self.ainbHelper(intervals[j], intervals[i]) == True:
                    try:
                        temp.remove(intervals[j])
                    except:
                        pass
                    j += 1
                else:
                    j += 1
            i += 1
        
        
        return len(temp)
    
    def ainbHelper(self, a: List[int], b: List[int]) -> bool:
        if a[0] < b[0]:
            return False
        if a[1] > b[1]:
            return False
        else: 
            return True


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        for i in range(len(intervals)):
            for j in range(len(intervals)):
                if i!=j:
                    if intervals[i]!=0 and intervals[j]!=0:
                        if intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]:
                            intervals[i] = 0
        
        c = 0
        for i in intervals:
            if i != 0:
                c += 1
        return c

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        s = set()
        for i, [a,b] in enumerate(intervals):
            for j, [c,d] in enumerate(intervals[i+1:]):
                if (c <= a and b <= d):
                    s.add((a,b))
                elif (a <= c and d <= b):
                    s.add((c,d))
        return len(intervals) - len(s)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        for i in range(len(intervals)-1):
            for j in range(len(intervals)-i-1):
                if intervals[j][0]>intervals[j+1][0]:
                    intervals[j],intervals[j+1]=intervals[j+1],intervals[j]
        i=0
        while True:
            while intervals[i][1]>=intervals[i+1][1]:
                intervals.pop(i+1)
                if (i+1)>len(intervals)-1:
                    break
            if (i+1)>len(intervals)-1:
                break
            if intervals[i][0]==intervals[i+1][0]:
                intervals.pop(i)
                if (i+1)>len(intervals)-1:
                    break
                else:
                    continue
            if (i+1)==len(intervals)-1:
                break
            i+=1
        return len(intervals)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        op=0
        if len(intervals)<2:
            return len(intervals)
        intervals.sort(key=lambda l1:l1[0])
        for j in intervals:            
            for k in intervals:
                if j[0]!=k[0] or j[1]!=k[1]:
                    if(j[0]>=k[0] and j[1]<=k[1]):
                        op+=1
                        break
        return len(intervals)-op
            
        
        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        sorted_intervals = sorted(intervals, key=lambda x:(x[0], -x[1]))
        covered = [False for interval in intervals]
        print(sorted_intervals)
        
        for outer_index, outer  in enumerate(sorted_intervals):
            for inner_index, inner in enumerate(sorted_intervals[outer_index+1:]):
                if outer[0] <= inner[0] and outer[1] >= inner[1]:
                    covered[inner_index+outer_index+1] = True
                    
        print(covered)
                    
        return sum((not cover for cover in covered))


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        L = len(intervals)
        rm = set()
        for i in range(L):
            for j in range(i+1,L):
                l1, r1 = intervals[i]
                l2,r2 = intervals[j]
                if l1<=l2 and r1>=r2:
                    if j not in rm:
                        rm.add(j)
                elif l1>=l2 and r1<=r2:
                    if i not in rm:
                        rm.add(i)
        return L-len(rm)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        count = [0]*len(intervals)
        for i in range(len(intervals)-1):
            a = intervals[i][0]
            b = intervals[i][1]
            for j in range(i+1,len(intervals)):
                x = intervals[j][0]
                y = intervals[j][1]
                if x <= a and b <= y:
                    # print(\"first\")
                    # print(x,y ,\"takes \",a,b)
                    count[i] = 1
                    # count[j] = 1
                elif a <= x and y <= b:
                    # print(a,b ,\"takes \",x,y)
                    # print(\"Second\")
                    # count[i] = 1
                    count[j] = 1
        ans = 0
        for c in count:
            if c == 0:
                ans +=1
        return ans


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        rm = {}
        for i in range(1,len(intervals)):
            for (a, b), (c, d) in zip(intervals[0:-i],intervals[i:]):
                if a >= c:
                    if b <= d:
                        rm[(a, b)] = True
                elif c >= a:
                    if d <= b:
                        rm[(c, d)] = True
        return len(intervals) - len(rm)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n=len(intervals)
        for i in range(n-1):
            for j in range(i+1,n):
                if intervals[i][0]>intervals[j][0]:
                    intervals[i],intervals[j]=intervals[j],intervals[i]
                elif intervals[i][0]==intervals[j][0]:
                    if intervals[i][1]<intervals[j][1]:
                        intervals[i],intervals[j]=intervals[j],intervals[i]
        l=[]
        print(intervals)
        for i in intervals:
            if l==[]:
                l.append(i)
            else:
                k1=l[-1]
                k2=i
                if k1[0]<=k2[0] and k1[1]>=k2[1]:
                    continue
                else:
                    l.append(i)
        return len(l)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        cover = [False for i in range(len(intervals))]
        for i in range(len(intervals)):
            for j in range(i+1, len(intervals)):
                a,b = intervals[i]
                c,d = intervals[j]
                if c <= a and b <= d:
                    cover[i] = True
                if a <= c and d <= b:
                    cover[j] = True
        ans = []
        print(cover)
        for i in range(len(cover)):
            if not cover[i]:
                ans.append(intervals[i])
        return len(ans)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x: x[1])
        k=0
        for i in range(len(intervals)):
            for j in range(0,len(intervals)):
                if i==j:
                    continue
                if (intervals[i][0]>=intervals[j][0]) and intervals[i][1]<=intervals[j][1]:
                    k+=1
                    break
        return len(intervals)-k
        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        toremove = set()
        for i in range(0, len(intervals)-1):
            for j in range(i+1, len(intervals)):
                s1, e1 = intervals[i]
                s2, e2 = intervals[j]
                
                if s1>=s2 and e1<=e2:
                    toremove.add(i)
                elif s2>=s1 and e2<=e1:
                    toremove.add(j)
        
        # res = []
        # for i, interval in enumerate(intervals):
        #     if i in toremove:
        #         continue
        #     res.append(interval)
        
        return len(intervals) - len(toremove)
                


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        def comparator(a, b):
            return a[0] - b[0]
        intervals.sort()
        removed = {}
        for index, interval in enumerate(intervals):
            for inner_index, inner_interval in enumerate(intervals):
                if index == inner_index:
                    continue
                    
                if index in removed or inner_index in removed:
                    continue
                    
                if inner_interval[0] >= interval[0] and inner_interval[1] <= interval[1]:
                    removed[inner_index] = True
                
        return len(intervals) - len(removed.keys())

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        tot = len(intervals)
        valid = [True] * len(intervals)
        for i in range(len(intervals)):
            if valid[i]:
                for j in range(len(intervals)):
                    if i == j:
                        continue
                    if valid[j] and intervals[j][0] >= intervals[i][0] and intervals[j][1] <= intervals[i][1]:
                        #print('Interval', intervals[j], 'removed by ', intervals[i])
                        valid[j] = False
                        tot -= 1
        return tot
                        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        removed = []
        for i in range(len(intervals) - 1):
            for j in range(i + 1, len(intervals)):
                if i in removed:
                    break
                if j in removed:
                    continue
                i_start, i_end = intervals[i]
                j_start, j_end = intervals[j]
                if i_start <= j_start and i_end >= j_end:
                    # i covers j
                    removed.append(j)
                elif i_start >= j_start and i_end <= j_end:
                    # j covers i
                    removed.append(i)
        return len(intervals) - len(removed)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        count = 0
        for i, [left, right] in enumerate(intervals):
            flag = True
            for j, [oleft, oright] in enumerate(intervals):
                if oleft <= left and right <= oright and i != j:
                    flag = False
                    continue
            if flag:
                count += 1
                
        
        return count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        intervals = sorted(intervals, key = lambda x: (x[0], - x[1]))
#        print(intervals)
        if len(intervals) == 1:
            return 1
        
        remove_indices = []
        
        for p1, (l1, r1) in enumerate(intervals[:-1]):
            
            for p2, (l2, r2) in enumerate(intervals[p1 + 1:]):
                
                if l1 <= l2 and r1 >= r2:
#                    print(p1, p2, remove_indices)
                    remove_indices.append(p2 + p1)
                elif l1 < l2 < r1:
#                    print(p1, p2, remove_indices)
                    continue
                else:
#                    print(p1, p2, remove_indices)
                    break
            
            
        return len([interval for idx, interval in enumerate(intervals) if idx not in remove_indices])

class Solution:
    def removeCoveredIntervals(self, interval: List[List[int]]) -> int:
        c=len(interval)
        for i in range(len(interval)):
            for j in range(len(interval)):
                if i!=j and interval[j][0]>=0 and interval[j][1]>=0:
                    if interval[i][0]<=interval[j][0] and interval[i][1]>=interval[j][1]:
                        c-=1
                        interval[j]=[-1,-1]
        return c

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        ref = [1]*n
        
        for i in range(n):
            for j in range(n):
                if i==j or not (ref[i] & ref[j]):
                    continue
                
                if intervals[i][0]<=intervals[j][0] and intervals[i][1]>=intervals[j][1]:
                    ref[j] = 0
        return sum(ref)

from copy import deepcopy

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intind = []
        for i in range(0,len(intervals)):
            a = intervals[i][0]
            b = intervals[i][1]
            for j in range(i+1, len(intervals)):
                c = intervals[j][0]
                d = intervals[j][1]
                if c <= a and b <= d:
                    intind.append(i)
                if a <= c and d <= b:
                    intind.append(j)
        return len(intervals)-len(set(intind))


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        exclusion_set = set()
        for i in range(len(intervals)):
            for j in range(i+1,len(intervals)):
                a,b = intervals[i]
                c,d = intervals[j]
                if c <= a and b <= d:
                    exclusion_set.add((a,b))
                if a <= c and d <= b:
                    exclusion_set.add((c,d))
        return len(intervals) - len(exclusion_set)                   

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        exclude = list()
        for ind, left in enumerate(intervals[:-1]):
            if left in exclude:
                continue
            for right in intervals[ind+1:]:
                if right in exclude:
                    continue
                elif (right[0] <= left[0] and left[1] <= right[1]):
                    exclude.append(left)
                    break
                elif(left[0] <= right[0] and right[1] <= left[1]):
                    exclude.append(right)
                else:
                    continue

                    
        return len(intervals) - len(exclude)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        removed = []
        for i,interval in enumerate(intervals):
            for i2 in range(i, len(intervals)):
                interval2 = intervals[i2]
                if i in removed:
                    break
                if i == i2 or i2 in removed:
                    continue
                if interval[0] >= interval2[0] and interval[1] <= interval2[1] and i not in removed:
                    removed += [i]
                if interval[0] <= interval2[0] and interval[1] >= interval2[1] and i2 not in removed:
                    removed += [i2]
                
        return len(intervals) - len(removed)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        total = len(intervals)
        for i, inner in enumerate(intervals):
            for o, outer in enumerate(intervals):
                if outer[0] <= inner[0] and outer[1] >= inner[1] and i != o:
                    #print(f\"inner {inner} outer {outer}\")
                    total -= 1
                    break
        return total

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        counter = 0
        l = len(intervals)
        for i in range(l):
            for j in range(l):
                if i!=j:
                    if intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]:
                        counter+=1
                        break
        return l-counter


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], -x[1]))
        intervals = list(map(tuple, intervals))
        covered = set()
        for i, iv in enumerate(intervals):
            if iv in covered:
                continue
            for iv2 in intervals[i+1:]:
                if iv2[0] > iv[1]:
                    break
                if iv[0] <= iv2[0] and iv[1] >= iv2[1]:
                    print(iv2)
                    covered.add(iv2)
                    
        return len(intervals) - len(covered)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        # Sort by start point
        # If two intervals shgare the same start point, put the longer one to be first
        intervals.sort(key = lambda x: (x[0], -x[1]))
        count = 0
        
        prev_end = 0
        for _, end in intervals:
            # if current interval is not covered
            # by the previos one
            if end > prev_end:
                count += 1
                prev_end = end
        
        return count
        
        
        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        op=0
        if len(intervals)<2:
            return len(intervals)
        for j in intervals:            
            for k in intervals:
                if j[0]!=k[0] or j[1]!=k[1]:
                    if(j[0]>=k[0] and j[1]<=k[1]):
                        op+=1
                        break
        return len(intervals)-op
            
        
        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        arr = []
        for val in intervals:
            for interval in intervals:
                if interval[0] == val[0] and interval[1] == val[1]:
                    continue
                if interval[0] <= val[0] and interval[1] >= val[1]:
                    break
            else:
                arr.append(val)
        return len(arr)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        i = 0
        result = len(intervals)
        
        while i < len(intervals)-1:
            
            a1, b1 = intervals[i]
            j = i+1
            remove_i = False
            while j<len(intervals):
                a2, b2 = intervals[j]
                # print(\"CHECK\", intervals[i], intervals[j], a1, b1, a2, b2)
                
                if a2 >= a1 and b2 <= b1:
                    # remove interval J
                    intervals = intervals[:j]+intervals[j+1:]
                    result -= 1
                    # print(\"REMOVE J\", intervals)
                    continue
                
                if a1 >= a2 and b1 <= b2:
                    # remote interval I
                    intervals = intervals[:i]+intervals[i+1:]
                    result -= 1
                    # print(\"REMOVE I\", intervals)
                    remove_i = True
                    break
                
                j = j+1
                
            if remove_i:
                continue
            i += 1
                    
        return result

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        ans = 0
        for i in range(len(intervals)):
            canFit = False
            for j in range(len(intervals)):
                if i == j: continue
                if intervals[i][0] >= intervals[j][0] and intervals[i][1] <= intervals[j][1]:
                    canFit = True
                    break
            if canFit == False:
                ans += 1
        return ans


# from ACgenerator.Y_Testing import get_code
from _bisect import bisect_left
from collections import Counter


def inversion(iterable):
    \"\"\"
    the number of j s.t (a[i] > a[j]) and (i < j) for each i
    Example:
        inversion([2, 3, 4, 2, 1])
        [1, 2, 2, 1, 0]
    \"\"\"
    iterable = discretization(iterable)[0]
    index = len(iterable)
    bit = Fenwick(index)
    result = [0] * index
    for item in reversed(iterable):
        index -= 1
        result[index] = bit.query(item)
        bit.update(item, 1)
    return result


def discretization(iterable):
    \"\"\" [1, 2, 4, 2, 5] -> [0, 1, 2, 1, 3] \"\"\"
    iterable = tuple(iterable)
    discrete_dict = dict(zip(sorted(set(iterable)), range(len(iterable))))
    return list(map(discrete_dict.__getitem__, iterable)), {v: k for k, v in discrete_dict.items()}


class Fenwick:
    \"\"\" Simpler FenwickTree \"\"\"

    def __init__(self, x):
        self.bit = [0] * x

    def update(self, idx, x):
        \"\"\"updates bit[idx] += x\"\"\"
        while idx < len(self.bit):
            self.bit[idx] += x
            idx |= idx + 1

    def query(self, end):
        \"\"\"calc sum(bit[:end])\"\"\"
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x

    def findkth(self, k):
        \"\"\"
        Find largest idx such that sum(bit[:idx]) < k
        (!) different from pyrival (just removed the '=')
        \"\"\"
        idx = -1
        for d in reversed(range(len(self.bit).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(self.bit) and k > self.bit[right_idx]:
                idx = right_idx
                k -= self.bit[idx]
        return idx + 1


class PointsCounter:
    def __init__(self, sorted_points):
        \"\"\"
        O(nlogn)
        Example:
            Quadrant([(0, 0), (1, 1), (2, 0), (2, 2), (3, 1), (4, 3)]).bottom_left
            -> [0, 1, 0, 2, 2, 5]
        \"\"\"
        self.data = sorted_points
        self._len = len(self.data)
        self.counter = Counter(self.data)
        self._xx, self._yy = zip(*self.data)
        self._xx = discretization(self._xx)[0]  # No sorting required
        self._yy = discretization(self._yy)[0]
        xy = tuple(zip(self._xx, self._yy))
        x_yy_size = xy[-1][0] + 1
        self._x_yy = [[] for ___ in range(x_yy_size)]  # reversed
        for x, y in xy:
            self._x_yy[x].append(y)
        # inversion
        bit = Fenwick(max(self._yy) + 1)
        self.bottom_left = []
        for nums in self._x_yy:
            for num in nums:
                self.bottom_left.append(bit.query(num))
            for num in nums:
                bit.update(num, 1)
        # other
        y_xx_size = max(self._yy) + 1
        self._y_xx = [[] for ___ in range(y_xx_size)]
        for x, y in xy:
            self._y_xx[y].append(x)

        self.same = [self.counter[self.data[index]] - 1 for index in range(self._len)]

        self.top = [0] * self._len
        self.bottom = [0] * self._len
        self.left = [0] * self._len
        self.right = [0] * self._len
        for index in range(self._len):
            x = self._xx[index]
            y = self._yy[index]
            self.bottom[index] = bisect_left(self._x_yy[x], y)
            self.top[index] = len(self._x_yy[x]) - self.bottom[index] - self.same[index]
            self.left[index] = bisect_left(self._y_xx[y], x)
            self.right[index] = len(self._y_xx[y]) - self.left[index] - self.same[index]

    def __len__(self):
        return self._len


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        points = [(p[0], -p[1]) for p in intervals]
        points.sort()
        pc = PointsCounter(points)
        ans = 0
        same = set()
        for i in range(len(pc)):
            if pc.bottom_left[i] or pc.left[i] or pc.bottom[i]:
                continue
            if pc.same[i]:
                same.add(pc.data[i])
            else:
                ans += 1
        return ans + len(same)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        
        
        for i in range(len(intervals)-1):
            
            if(intervals[i][0]==-1):
                continue
            
            
            for j in range(i+1,len(intervals)):
                t=intervals[i]
                tn=intervals[j]
                
                
                if(t[0]<=tn[0] and tn[1]<=t[1]):
                    intervals[j][0],intervals[j][1]=-1,-1
            
                elif(tn[0]<=t[0] and t[1]<=tn[1]):
                    intervals[i][0],intervals[i][1]=-1,-1
                    
        
        count=0
        
        for i in intervals:
            if(i[0]!=-1):
                count+=1
        
        return(count)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n_intervals = len(intervals)
        if intervals:
            intervals = sorted(intervals, key=lambda x: x[0] - x[1])
            i = len(intervals) - 1
            while i > 0:
                interval_i = intervals[i]
                j = i - 1
                while j >= 0:
                    # print(interval_i, intervals[j])
                    if (intervals[j][0] <= interval_i[0]) and (intervals[j][1] >= interval_i[1]):
                        n_intervals -= 1
                        break
                    j -= 1
                i -= 1
        return n_intervals

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        cov = 0
        
        # First covers second?
        def covered(first,second):
            return (first[0] <= second[0]) and (second[1] <= first[1])
        
        for pos,inter1 in enumerate(intervals):
            for checkpos,inter2 in enumerate(intervals):
                # print(inter1, inter2)
                if pos != checkpos and covered(inter2,inter1): 
                    # print(\"covered\")
                    cov += 1
                    break
                    
        return len(intervals) - cov

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        count = len(intervals)
        for i in range(len(intervals)):
            for j in range(len(intervals)):                
                if((i!=j) & (intervals[i][0] >= intervals[j][0]) & (intervals[i][1] <= intervals[j][1])): 
                    count=count-1
                    break
        return count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        covered=0
        same=0
        for i in range(len(intervals)):
            for j in range(len(intervals)):
                if intervals[i][0]==intervals[j][0] and intervals[j][1]==intervals[i][1]:
                    continue
                elif intervals[i][0]>=intervals[j][0] and intervals[j][1]>=intervals[i][1]:
                    covered+=1
                    break
        return len(intervals)-covered
        #return len(intervals)-covered+same
                    


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        return self.m1_sort(intervals)
    
    
    def m1_sort(self, intervals):
        intervals.sort(key=lambda x: x[1], reverse=True)
        intervals.sort(key=lambda x: x[0])
        
        count = 0
        max_end = 0
        for interval in intervals:
            if interval[1] > max_end:
                max_end = interval[1]
                count += 1
        return count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        a = self.checkInterval(intervals)
        return len(a)

    def checkInterval(self, intervals) -> List[List[int]]:
        if len(intervals) == 1:
            return [intervals[0]]
        else:
            front = intervals[0]
            back = self.checkInterval(intervals[1:])
            if not back: return front
            s, e = front[0], front[1]
            irrelevant = list([interval for interval in back if interval[0] <= s and e <= interval[1]])
            if len(irrelevant): 
                return back
            filtered = list([interval for interval in back if not (s <= interval[0] and interval[1] <= e)])
            return [front] + filtered


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x: (x[0], -x[1]))
        q = [intervals[0][1]]
        counter = 0
        for a,b in intervals[1:]:
            t = [x for x in q]
            flag = 0
            for v in q:
                if a > v:
                    t.remove(v)
                    flag = 1
                elif b <= v:
                    counter += 1
                    break
                else:
                    flag = 1
            if flag == 1:
                t.append(b)
            q = t
        return len(intervals) - counter
        


class Solution:
    
    def checkIntvl(self, a: List[int], b: List[int]) -> bool:
        return b[0] <= a[0] and b[1] >= a[1]

    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        count = 0
        for i, i1 in enumerate(intervals):
            is_covered = False
            for j, i2 in enumerate(intervals):
                if i == j:
                    continue
                else:
                    is_covered = self.checkIntvl(i1, i2)
                    if is_covered:
                        break
            if not is_covered:
                count += 1
        return count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda interval: interval[1] - interval[0])
        # print(intervals)
        counter = 0
        i = 0
        n = len(intervals)
        for i in range(n):
            covered = False
            for j in range(i+1, n):
                if self.cover(intervals[j], intervals[i]):
                    covered = True
                    break
            if not covered:
                counter += 1
        return counter
                
            
        
    def cover(self, interval1, interval2):
        # return whether interval1 cover interval2
        return interval1[0] <= interval2[0] and interval1[1] >= interval2[1] 


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        covered = set()
        p1 = 0
        
        while p1 < len(intervals):
            if p1 in covered:
                p1 +=1
                continue
            p2 = p1 + 1
            while p2 <  len(intervals):
                if intervals[p1][0] <= intervals[p2][0] and intervals[p2][1] <= intervals[p1][1]:
                    covered.add(p2)
                elif intervals[p2][0] <= intervals[p1][0] and intervals[p1][1] <= intervals[p2][1]:
                    covered.add(p1)
                p2 += 1
            p1 += 1
                
        return len(intervals) - len(covered)
        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        def covers(interval, byinterval):
            return interval[0] >= byinterval[0] and interval[1] <= byinterval[1]
        
        ret = 0
        for i in range(len(intervals)):
            iscovered = False
            for j in (x for x in range(len(intervals)) if x != i):
                if covers(intervals[i], intervals[j]):
                    iscovered = True
                    break
            if not iscovered:
                ret += 1
        return ret

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        deleted = set()
        for idx, interval in enumerate(intervals):
            if str(interval) in deleted:
                continue
            for other in intervals[idx + 1:]:
                if interval[0] <= other[0] and interval[1] >= other[1]:
                    deleted.add(str(other))
                elif interval[0] >= other[0] and interval[1] <= other[1]:
                    deleted.add(str(interval))
        return len(intervals) - len(deleted)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0],-x[1]))
        ub = [x[1] for x in intervals]
        d = [(x - max(ub[:i+1]))<=0 for i,x in enumerate(ub[1:])]
        return len(intervals)-sum(d)


class Solution:

  def compare(self, intervalA: List[int], intervalB: List[int]) -> int:
    if (intervalA[0] <= intervalB[0] and intervalA[1] >= intervalB[1]):
      return 1
    if (intervalB[0] <= intervalA[0] and intervalB[1] >= intervalA[1]):
      return -1
    return 0 

  def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
    intervals.sort(key = lambda x: x[0])
    result = len(intervals)
    index = 0
    while index < len(intervals):
      itemA = intervals[index]
      removes = []
      for i in range(index + 1, len(intervals)):
        itemB = intervals[i]
        comp = self.compare(itemA, itemB)
        if (comp == 0):
          continue
        if (comp == 1):
          removes.append(i)
        elif (comp == -1 and index not in removes):
          removes.append(index)
      
      if (len(removes) == 0):
        index += 1 
      else: 
        removes.sort()
        removes.reverse()
        for k in range(len(removes)):
          intervals.remove(intervals[removes[k]])
        if (index not in removes):
          index += 1
      
      result -= len(removes)

    return result 

class Solution:
    def removeCoveredIntervals(self, intervals):
        result = 0
        for i in range(len(intervals)):
            covered = False
            for j in range(len(intervals)):
                if i == j: continue
            
                if self.covered(intervals[i], intervals[j]):
                    covered = True
                    break
                
            
            if not covered:
                result += 1
        
        return result
                
        
    # Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d
    def covered(self, i1, i2):
        c = i2[0]
        d = i2[1]
        
        a = i1[0]
        b = i1[1]
        
        return c <= a and b <= d

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        sorted_intervals = sorted(intervals, key=lambda x: (x[0], -x[1]))
        
        new_intervals = []
        new_intervals.append(sorted_intervals[0])
        for i in sorted_intervals:
            n = new_intervals[-1]
            if i[0] >= n[0] and i[1] <= n[1]:
                continue
            new_intervals.append(i)
        return len(new_intervals)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        tree = {}
        for x, y in intervals:
            cursor = tree
            if not tree:
                tree['value'] = (x, y)
            else:
                while True:
                    if x < cursor['value'][0]:
                        tmp = cursor.get('left', {})
                        if tmp:
                            cursor = tmp
                        else:
                            cursor['left'] = {'value': (x, y)}
                            break
                    elif x > cursor['value'][0]:
                        tmp = cursor.get('right', {})
                        if tmp:
                            cursor = tmp

                        else:
                            cursor['right'] = {'value': (x, y)}
                            break
                    else:
                        if y > cursor['value'][1]:
                            tmp = cursor.get('left', {})
                            if tmp:
                                cursor = tmp
                            else:
                                cursor['left'] = {'value': (x, y)}
                                break
                        elif y < cursor['value'][1]:
                            tmp = cursor.get('right', {})
                            if tmp:
                                cursor = tmp

                            else:
                                cursor['right'] = {'value': (x, y)}
                                break
                        else:
                            break
        buff = [tree]
        count, last = 0, None
        while buff:
            while buff[-1].get('left', None):
                buff.append(buff[-1]['left'])
            while buff and not buff[-1].get('right', None):
                this = buff.pop(-1)
                if count == 0:
                    count, last = 1, this['value'][1]
                else:
                    if this['value'][1] > last:
                        count, last = count + 1, this['value'][1]

                #ret.append(buff.pop(-1))
            if buff:
                #ret.append(buff.pop(-1))
                this = buff.pop(-1)
                if count == 0:
                    count, last = 1, this['value'][1]
                else:
                    if this['value'][1] > last:
                        count, last = count + 1, this['value'][1]
                buff.append(this['right'])
        return count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        count = 0
        for i in range(len(intervals)) :
            if intervals[i] != None:
                for j in range(len(intervals)):
                    if i != j and intervals[j]:
                        if (intervals[j][0] <= intervals[i][0]) and (intervals[i][1] <= intervals[j][1]):
                            intervals[i] = None
                            break

        for interval in intervals:
            if interval: 
                count += 1
            
        return count


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        valid = []
        for (index, (i, j)) in enumerate(intervals):
            for (ii, jj) in intervals[:index] + intervals[(index + 1):]:
                if ii <= i and jj >= j:
                    break
            else:
                valid.append([i, j])
        print(valid)
        return len(valid)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 0:
            return 0
        elif len(intervals) == 1:
            return 1

        remove_indices = set()
        for i in range(len(intervals)):
            a, b = intervals[i]
            for j in range(i + 1, len(intervals)):
                c, d = intervals[j]
                if a != c or b != d:
                    if a >= c and b <= d:
                        # remove [a, b]
                        remove_indices.add(i)
                        break
                    elif c >= a and d <= b:
                        # remove [c, d]
                        remove_indices.add(j)
        return len(intervals) - len(remove_indices)

class Solution:
    
    def covered(self, interval_1, interval_2):
        return interval_2[0] <= interval_1[0] and interval_2[1] >= interval_1[1]
    
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        
        i = 0
        while (i < len(intervals)):
            j = 0
            while (j < len(intervals)):
                print((len(intervals), i, j))
                if j == i or intervals[j][0] > intervals[i][0]:
                    j += 1
                    continue
                elif self.covered(intervals[i], intervals[j]):
                    intervals.pop(i)
                    i -= 1
                    break
                else:
                    j += 1
                    continue
            i += 1
        
        
            
        return len(intervals)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        table = dict()
        for interval in intervals:
            if interval[0] not in intervals:
                table[interval[0]] = interval[1]
            else:
                if interval[1] > table[interval[0]]:
                    table[interval[0]] = interval[1]
        count = len(table) + 1
        keys = list(table.keys())
        cover = table[keys[0]]
        for key in table.keys():
            if table[key] <= cover:
                count -= 1
            else:
                cover = table[key]
        return count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        # for each interval, check all other intervals to see if it is
        # covered by some other interval
        i = 0
        
        while (i < len(intervals)):
            current_int = intervals[i]
            
            # check all other intervals
            for j in range(i + 1, len(intervals)):
                int1 = intervals[j]
                
                # if current interval covers this interval or this
                # interval covers the current interval, remove the 
                # interval that is covered
                if (current_int[0] <= int1[0] and current_int[1] >= int1[1]):
                    intervals.remove(int1)
                    i -= 1
                    break
                elif (int1[0] <= current_int[0] and int1[1] >= current_int[1]):
                    intervals.remove(current_int)
                    i -= 1
                    break
            
            i += 1
        
        return len(intervals)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        def isCovered(interval, candidates):
            for c in candidates:
                if c[0] <= interval[0] and c[1] >= interval[1]:
                    return True
            return False
        
        cnt = 0
        for i, interval in enumerate(intervals):
            if not isCovered(interval, intervals[:i]+intervals[i+1:]):
                cnt += 1
        return cnt

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        a = self.checkInterval(intervals)
        print(a)
        return len(a)

    def checkInterval(self, intervals) -> List[List[int]]:
        if len(intervals) == 1:
            return [intervals[0]]
        else:
            front = intervals[0]
            back = self.checkInterval(intervals[1:])
            if not back: return front
            print(('f,b',front, back))
            s, e = front[0], front[1]
            irrelevant = list([interval for interval in back if interval[0] <= s and e <= interval[1]])
            if len(irrelevant): 
                print(('irrel',back))
                return back
            filtered = list([interval for interval in back if not (s <= interval[0] and interval[1] <= e)])
            print(('continue',front, filtered))
            return [front] + filtered


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: [x[0], -x[1]])
        prev_end, count = 0, 0
        
        for _, curr_end in intervals:
            if prev_end < curr_end:
                count += 1
                prev_end = curr_end
        
        return count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        arr=[0]*len(intervals)
        for i in range(len(intervals)):
            for j in range(len(intervals)):
                if(i!=j and arr[j]!=-1):
                    if(intervals[i][0]>=intervals[j][0] and intervals[i][1]<=intervals[j][1]):
                        arr[i]=-1
                        break
        ans=0
        for i in arr:
            if(i!=-1):
                ans+=1
        return ans

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        leftsorted = sorted(intervals, key = lambda x : (x[0], x[1]))
        i = 0
        while i < len(leftsorted) - 1:
            if leftsorted[i][0] == leftsorted[i+1][0]:
                intervals.remove(leftsorted[i])
                
            i += 1
        
        rightsorted = sorted(intervals, key=lambda x: (x[1], x[0]))
        i = 0
        while i < len(rightsorted) - 1:
            if rightsorted[i][1] == rightsorted[i + 1][1]:
                intervals.remove(rightsorted[i + 1])

            i += 1
        
        leftsorted  = sorted(intervals, key = lambda x : (x[0], x[1]))
        rightsorted  = sorted(intervals, key = lambda x : (x[1], x[0]))
        
        lremain = len(leftsorted)
        i, j = 0, 0
        
        removed = []
        while i < lremain and j < lremain:
            # if leftsorted[i] in removed:
            if leftsorted[i] not in intervals:
                i += 1
            elif leftsorted[i] != rightsorted[j]:
                intervals.remove(rightsorted[j])
                # removed.append(rightsorted[j])
                j += 1
            else: 
                i += 1
                j += 1
                # while leftsorted[i] not in intervals:
                #     i += 1
                #     if i == lremain:
                #         break
        
        
        
#         removed = []
#         for i in range(len(leftsorted)):
#             if leftsorted[i] not in intervals:
#                 continue
#             if leftsorted[i] != rightsorted[i]:
#                 intervals.remove(rightsorted[i])
        print(intervals)
        return len(intervals)
                             
        
            


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key=lambda l:l[0])
        range_list = [item for item in intervals]
        for item in intervals:
            for range_item in range_list:
                a = item[0]
                b = item[1]
                c = range_item[0]
                d = range_item[1]
                if c == a and b == d:
                    break;
                if c <= a and b <= d and item in range_list:
                    range_list.remove(item)
                if a <= c and d <= b:
                    range_list.remove(range_item)
        range_list_2 = range_list
        
    
        print(range_list)
        return len(range_list)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        l = len(intervals)
        #sorting the list so each element can only be compared with next element
        intervals.sort(key = lambda sl: sl[0],reverse=True)
        #remove duplicate elements 
        res = l
        print(intervals)
        for i in range(l-1,0,-1):
            if (intervals[i-1][0]>=intervals[i][0] and intervals[i-1][1]<=intervals[i][1]):
                intervals.remove(intervals[i-1])
                print((intervals[i-1]))
                res -= 1
        return res
    
        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        l = intervals[:]
        
        for i in range(len(intervals)):
            flag = 0
            for j in range(len(intervals)):
                if i!=j:
                    if intervals[i][0] in range(intervals[j][0],intervals[j][1]+1) and intervals[i][1] in range(intervals[j][0],intervals[j][1]+1):
                        flag = 1
                        l.remove(intervals[i])
                        break
                if flag==1:
                    break
        return len(l)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        def checkCovered(self, A, B):
            if B[0]<=A[0] and A[1]<=B[1]:
                return True
            else:
                return False
        
        res = len(intervals)
        
        for i,interval in enumerate(intervals):
            tmp = intervals[:i]+intervals[i+1:]
            for each in tmp:
                if checkCovered(self,interval,each):
                    res-=1
                    break
        return res

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        len_interval = len(intervals)
        if len_interval == 1:
            return 1
        count = len_interval
        for i in range(len_interval):
            part_intervals = intervals[:i]+intervals[i+1:]
            for interval in part_intervals:
                if self.isOverlapping(intervals[i], interval):
                    count -= 1
                    break
        return count

    def isOverlapping(self,
                      interval_1: List[int],
                      interval_2: List[int]) -> bool:
        if interval_2[0] <= interval_1[0] and interval_1[1] <= interval_2[1]:
            return True
        else:
            return False

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        removed = set()
        for i in range(len(intervals)-1):
            if i in removed:
                pass
            for j in range(i+1, len(intervals)):
                if intervals[i][0] <= intervals[j][0] <= intervals[j][1] <= intervals[i][1]:
                    removed.add(j)
                elif intervals[j][0] <= intervals[i][0] <= intervals[i][1] <= intervals[j][1]:
                    removed.add(i)
                    break
        return len(intervals) - len(removed)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x:x[0])
        i=1
        while i<len(intervals):
            a=intervals[i][0]
            b=intervals[i][1]
            c=intervals[i-1][0]
            d=intervals[i-1][1]
            if c<=a and d>=b:
                intervals.pop(i)
            else:
                i+=1
        i=len(intervals)-2
        print(i)
        print((len(intervals)))
        while i>=0:
            a=intervals[i][0]
            b=intervals[i][1]
            c=intervals[i+1][0]
            d=intervals[i+1][1]
            if c<=a and d>=b:
                intervals.pop(i)
            i-=1
        return len(intervals)
                           


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        d = {}
        for l, r in intervals:
            if l not in d:
                d[l] = []
            d[l].append(r)
        dd = []
        for l in sorted(d.keys()):
            dd.append([l, max(d[l])])
        # print(dd)
        for i in range(len(dd)):
            for j in range(i+1, len(dd)):
                if dd[i] and dd[j] and dd[i][1] >= dd[j][1]:
                    dd[j] = False
        # print(dd)
        # print('---------------------')
        ans = 0
        for ddd in dd:
            if ddd:
                ans += 1
        return ans

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        count = length = len(intervals)
        removedIdx = set()
        for i in range(length-1):
            for j in range(i+1, length):
                if i in removedIdx or j in removedIdx:
                    continue
                a, b = intervals[i][0], intervals[i][1]
                c, d = intervals[j][0], intervals[j][1]
                
                if a <= c and b >= d:
                    count -= 1
                    removedIdx.add(j)
                elif c <= a and d >= b:
                    count -= 1
                    removedIdx.add(i)

                    
        return count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        exists = [True] * len(intervals)
        for i in range(len(intervals)-1):
            for j in range(i+1, len(intervals)):
                if exists[i] and exists[j]:
                    result = self.isCovered(intervals[i], intervals[j])
                    if result == 1:
                        exists[j] = False
                    elif result == -1:
                        exists[i] = False
                    else:
                        pass
        return sum(exists)
    def isCovered(self, a: List[int], b: List[int]) -> int:
        if a[0] <= b[0] and a[1] >= b[1]:
            return 1
        elif a[0] >= b[0] and a[1] <= b[1]:
            return -1
        else:
            return 0
        


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        isRemoved = [False] * n
        numRemoved = 0
        
        for i in range(n-1):

            for j in range(i+1, n):
                if not isRemoved[j] and not isRemoved[i]:
                    if (intervals[i][0] <= intervals[j][0]) and (intervals[i][1] >= intervals[j][1]): # remove j
                        isRemoved[j] = True
                        numRemoved += 1
                    elif (intervals[i][0] >= intervals[j][0]) and (intervals[i][1] <= intervals[j][1]): # remove i
                        isRemoved[i] = True
                        numRemoved += 1
        print(isRemoved)           
        return n-numRemoved

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        c=0
        if len(intervals)==1:
            return 1
        else:
            for i in range(len(intervals)):
                print(\"i\")
                print(i)
                for j in range(len(intervals)):
                    print(\"j\")
                    print(j)
                    if i!=j and intervals[j][0]<=intervals[i][0] and intervals[i][1]<=intervals[j][1]:
                        c+=1
                        break
            return len(intervals)-c
                         

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        removed = 0
        for i in range(len(intervals)):  # 7
            for j in range(len(intervals)):  # 7 - > 7
                if i == j:
                    continue
                print(i, j)
                a, b = intervals[i]
                c, d = intervals[j]
                if c <= a and b <= d:
                    removed += 1
                    break
        
        return len(intervals) - removed

class Solution1:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals)
        
        l, r = intervals[0]
        for i in range(1, len(intervals)):
            start, end = intervals[i]
            # Start is bigger than l because intervals is sorted!
            if end <= r:  # first interval covers second!
                r = end
            else:
                
                pass

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        if len(intervals) < 2: return n
        condition = True
        while condition:
            indexes = []
            condition = False
            for ind0 in range(n):
                for ind1 in range(ind0 + 1, n):
                    # if intervals[ind0] covered by intervals[ind1]
                    if intervals[ind1][0] <= intervals[ind0][0] and intervals[ind0][1] <= intervals[ind1][1]:
                        indexes.append(ind0)
                        if not condition: condition = True
                        break
                    # if intervals[ind1] covered by intervals[ind0]
                    elif intervals[ind0][0] <= intervals[ind1][0] and intervals[ind1][1] <= intervals[ind0][1]:
                        indexes.append(ind1)
                        if not condition: condition = True
            
            indexes = list(set(indexes))       
            for index in sorted(indexes, reverse=True):
                del intervals[index]
        
            n = len(intervals)
            if n < 2: return n
        return n

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        removed = 0
        for i in range(len(intervals)):  # 7
            for j in range(len(intervals)):  # 7 - > 7
                if i == j:
                    continue
                print((i, j))
                a, b = intervals[i]
                c, d = intervals[j]
                if c <= a and b <= d:
                    removed += 1
                    break
        
        return len(intervals) - removed


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x:x[0])
        i=1
        while i<len(intervals):
            a=intervals[i][0]
            b=intervals[i][1]
            c=intervals[i-1][0]
            d=intervals[i-1][1]
            if c<=a and d>=b:
                intervals.pop(i)
            else:
                i+=1
        i=len(intervals)-2
        print(i)
        print((len(intervals)))
        while i>=0:
            a=intervals[i][0]
            b=intervals[i][1]
            c=intervals[i+1][0]
            d=intervals[i+1][1]
            if c<=a and d>=b:
                intervals.pop(i)
                i-=1
            else:
                i-=1
        return len(intervals)
                           


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        result = set()
        intervals.sort(key=lambda x:(x[0],-x[1]))
        for i in range(len(intervals)):
            for j in range(i+1,len(intervals)):
                if j not in result and intervals[i][1] >= intervals[j][1]:
                    result.add(j)
        return len(intervals)-len(result)        

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        removed = 0
        removed_list = {}
        
        for i in range(len(intervals)):
            for j in range(i+1,len(intervals)):
                if i in removed_list or j in removed_list:
                    continue
                elif (intervals[j][0] <= intervals[i][0] <= intervals[j][1] and intervals[j][0] <= intervals[i][1] <= intervals[j][1]):
                    removed_list[i] = True    
                    removed += 1                
                elif (intervals[i][0] <= intervals[j][0] <= intervals[i][1] and intervals[i][0] <= intervals[j][1] <= intervals[i][1]):
                    removed_list[j] = True
                    removed += 1
        
        return len(intervals) - removed
                


from heapq import heapify, heappush, heappop
START = 0 
END = 1

class BinaryTreeNode(object):
    __slots__ = [\"val\", \"left\", \"right\", \"parent\", \"height\"]
    def __init__(self, val, parent=None):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1
        self.parent = parent
        
    def min(self):
        node = self
        while node.left:
            node = node.left
        return node.val
        
    def setHeight(self):
        lh = self.left.height if self.left else 0
        rh = self.right.height if self.right else 0
        self.height = 1 + max(lh, rh)
        
    def balanceF(self):
        lh = self.left.height if self.left else 0
        rh = self.right.height if self.right else 0
        return lh - rh
    
    def nextNode(self):
        isLeft = lambda c: c.parent and c.parent.left is c
        
        current = self
        if current.right:
            current = current.right
            while current.left:
                current = current.left
            return current
        else:
            while current.parent and not isLeft(current):
                current = current.parent
            return current.parent
            
    def prevNode(self):
        isLeft = lambda c: c.parent and c.parent.left is c
        
        current = self
        if current.left:
            current = current.left
            while current.right:
                current = current.right
            return current
        else:
            while current.parent and isLeft(current):
                current = current.parent
            return current.parent

    def validate(self,min_value=None, max_value=None):
        if min_value is not None:
            if self.val < min_value:
                print(\"bad_node\")
                return False
        if max_value is not None:
            if self.val > max_value:
                print(\"bad_node\")
                return False

        l, r = True, True
        if self.left:
            l = self.left.parent is self and self.left.validate(min_value, self.val)
        if self.right:
            r = self.right.parent is self and self.right.validate(self.val, max_value)
        
        return l and r
        

class AvlTree(object):
    __slots__ = [\"root\", \"size\", \"min\"]
    def __init__(self):
        self.root = None
        self.size = 0
        self.min = None
        
    def add(self, val, node=None):
        if not self.root:
            self.root = BinaryTreeNode(val)
            self.size += 1
            return self.root
        
        if node is None:
            node = self.root
            
        if val < node.val:
            if node.left:
                added = self.add(val, node.left)
            else:
                node.left = BinaryTreeNode(val, node)
                self.size += 1
                added = node.left  
        else:
            if node.right:
                added = self.add(val, node.right)
            else:
                node.right = BinaryTreeNode(val, node)
                self.size += 1
                added = node.right 
    
        node.setHeight()
        self.balance(node)
        if self.min is None or self.min > val:
            self.min = val
        return added
        
    def balance(self, node):
        if node.balanceF() > 1:
            if node.left.balanceF() > 0:
                self.rotateRight(node)
            else:
                self.rotateLeft(node.left)
                self.rotateRight(node)
        elif node.balanceF() < -1:
            if node.right.balanceF() < 0:
                self.rotateLeft(node)
            else:
                self.rotateRight(node.right)
                self.rotateLeft(node)

    def swapNodes(self, nodeA, nodeB):
        if nodeA.parent is nodeB:
            return self.swapNodes(nodeB, nodeA)
            
        a_p, a_l, a_r, a_h = nodeA.parent, nodeA.left, nodeA.right, nodeA.height
        b_p, b_l, b_r, b_h = nodeB.parent, nodeB.left, nodeB.right, nodeB.height

        nodeA.parent, nodeA.left, nodeA.right, nodeA.height = b_p, b_l, b_r, b_h
        nodeB.parent, nodeB.left, nodeB.right, nodeB.height = a_p, a_l, a_r, a_h

   
        if nodeA.left is nodeA:
            nodeA.left = nodeB
        elif nodeA.right is nodeA:
            nodeA.right = nodeB
        if nodeB.left is nodeB:
            nodeB.left = nodeA
        elif nodeB.right is nodeB:
            nodeB.right = nodeA
        if nodeA.right:
            nodeA.right.parent = nodeA
        if nodeA.left:
            nodeA.left.parent = nodeA
        if nodeB.right:
            nodeB.right.parent = nodeB
        if nodeB.left:
            nodeB.left.parent = nodeB

        if nodeA.parent is None:
            self.root = nodeA
        elif nodeA.parent.left is nodeB:
            nodeA.parent.left = nodeA
        else:
            nodeA.parent.right = nodeA
        if nodeB.parent is None:
            self.root = nodeB
        elif nodeB.parent.left is nodeA:
            nodeB.parent.left = nodeB
        else:
            nodeB.parent.right = nodeB
            
                
    def remove(self, node):
        self.size -= 1
        while node.left or node.right:
            replace = None
            if not node.right:
                replace = node.left
            elif not node.left:
                replace = node.right
            if replace:
                if node.parent is None:
                    self.root = replace
                elif node.parent.left is node:
                    node.parent.left = replace
                else:
                    node.parent.right = replace
                replace.parent = node.parent
                node.parent = replace
                break
            else:
                swap = node.nextNode()
                self.swapNodes(node, swap)
            
        if node.parent is None:
            self.root = None
        else:
            if node.parent.left is node:
                node.parent.left = None
            elif node.parent.right is node:
                node.parent.right = None
            
        current = node.parent
        while current:
            current.setHeight()
            #self.balance(current)
            current = current.parent
        if self.size == 0:
            self.min = None
        elif node.val == self.min:
            self.min = self.root.min()
                
                
    def setParent(self, parent, new_node):
        if parent is None:
            self.root = new_node
        elif new_node.val < parent.val:
            parent.left = new_node
        else:
            parent.right = new_node
        new_node.parent = parent
        
    def rotateLeft(self, node):
        nr = node.right
        node.right = nr.left
        if nr.left:
            nr.left.parent = node
        nr.left = node
        old_parent = node.parent
        node.parent = nr
        self.setParent(old_parent, nr)
        node.setHeight()
        nr.setHeight()
        
    def rotateRight(self, node):
        nl = node.left
        node.left = nl.right
        if nl.right:
            nl.right.parent = node
        nl.right = node
        old_parent = node.parent
        node.parent = nl
        self.setParent(old_parent, nl)
        node.setHeight()
        nl.setHeight()        
    
    def __len__(self):
        return self.size
    
    
class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        events = [(a[0], START, -a[1] , i) for i, a in enumerate(intervals)]
        events.extend([(a[1], END, -a[0] , i) for i, a in enumerate(intervals)])
        events.sort()
        
        tree = AvlTree()
        nodes = [None]*len(intervals)
        answer = len(intervals)
        while len(events) > 0:
            event = heappop(events)
            if event[1] == START:
                nodes[event[3]] = tree.add(event[0])
            else:
                tree.remove(nodes[event[3]])
                #print(tree.min)
                if tree.min is not None and tree.min <= intervals[event[3]][0]:
                    #print(event)
                    answer -= 1
        return answer
                
                
            
            
            
        

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        answers = []
        for i in intervals:
            cints = intervals.copy()
            cints.remove(i)
            if all(map(lambda j: i[0] < j[0] or i[1] > j[1], cints)):
                answers.append(i)
        
        return len(answers)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        #h=[[1,4],[3,6],[2,8]]
#print(h)
        intervals.sort()
        n=len(intervals)
        i=0
        while i<len(intervals):
            j=i+1
            while j<len(intervals):
                if intervals[i][0]<=intervals[j][0] and intervals[i][1]>=intervals[j][1]:
                    intervals.pop(j)
            #print(intervals)
                    j=i+1
                elif intervals[i][0]>=intervals[j][0] and intervals[i][1]<=intervals[j][1]:
                    intervals.pop(i)
            #print(intervals)
                    j=i+1
                else:
                    j=j+1
            i=i+1
        return len(intervals)

class Tree:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __lt__(self, other):
        if self.val[0] < other.val[0]: return True

        elif self.val[0] > other.val[0]: return False

        else: return self.val[1] > other.val[1]

    #def __le__(self, other): return self < other or self.val == other.val

    #def __gt__(self, other): return not self <= other

    #def __ge__(self, other): return not self < other

    #def __eq__(self, other): return self <= other and self >= geother

    #def __neq__(self, other): return not self == other

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        tree = Tree(val=tuple(intervals[0]))
        for x, y in intervals[1:]:
            this = Tree((x, y))
            cursor = tree
            while True:
                if this < cursor:
                    if cursor.left:
                        cursor = cursor.left
                    else:
                        cursor.left = this
                        break
                elif cursor < this:
                    if cursor.right:
                        cursor = cursor.right
                    else:
                        cursor.right = this
                        break
                else:
                    break

        buff = [tree]
        count, last = 0, None
        while buff:
            while buff[-1].left: buff.append(buff[-1].left)
            while buff and not buff[-1].right:
                this = buff.pop(-1)
                if count == 0: count, last = 1, this.val[1]

                else:
                    if this.val[1] > last: count, last = count + 1, this.val[1]

            if buff:
                this = buff.pop(-1)
                if count == 0: count, last = 1, this.val[1]

                else:
                    if this.val[1] > last: count, last = count + 1, this.val[1]

                buff.append(this.right)

        return count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:       
        covered_intervals = set()
        for a in intervals:
            for b in intervals:
                if a is b or tuple(b) in covered_intervals:
                    continue
                if covered(a, b):
                    covered_intervals.add(tuple(a))
                    break
                    
        return len(intervals) - len(covered_intervals)
                    
        
def covered(a, b):
    return b[0] <= a[0] and a[1] <= b[1]

class Tree:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __lt__(self, other):
        if self.val[0] < other.val[0]: return True

        elif self.val[0] > other.val[0]: return False

        else: return self.val[1] > other.val[1]

    #def __le__(self, other): return self < other or self.val == other.val

    #def __gt__(self, other): return not self <= other

    #def __ge__(self, other): return not self < other

    #def __eq__(self, other): return self <= other and self >= other

    #def __neq__(self, other): return not self == other

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        tree = Tree(val=tuple(intervals[0]))
        for x, y in intervals[1:]:
            this = Tree((x, y))
            cursor = tree
            while True:
                if this < cursor:
                    if cursor.left:
                        cursor = cursor.left
                    else:
                        cursor.left = this
                        break
                elif cursor < this:
                    if cursor.right:
                        cursor = cursor.right
                    else:
                        cursor.right = this
                        break
                else:
                    break

        buff = [tree]
        count, last = 0, None
        while buff:
            while buff[-1].left: buff.append(buff[-1].left)
            while buff and not buff[-1].right:
                this = buff.pop(-1)
                if count == 0: count, last = 1, this.val[1]

                else:
                    if this.val[1] > last: count, last = count + 1, this.val[1]

            if buff:
                this = buff.pop(-1)
                if count == 0: count, last = 1, this.val[1]

                else:
                    if this.val[1] > last: count, last = count + 1, this.val[1]

                buff.append(this.right)

        return count

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key = lambda x: (x[0], - x[1]))
        endingval = 0
        res = 0
        for _,end in intervals:
            if endingval < end:
                endingval = end
                res += 1
        return res

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 0:
            return 0
        elif len(intervals) == 1:
            return 1

        remove_indices = []
        for i in range(len(intervals)):
            a, b = intervals[i]
            for j in range(i + 1, len(intervals)):
                c, d = intervals[j]
                if a != c or b != d:
                    if a >= c and b <= d:
                        # remove [a, b]
                        remove_indices.append(i)
                        break
                    elif c >= a and d <= b:
                        # remove [c, d]
                        remove_indices.append(j)

        return len([intervals[i] for i in range(len(intervals)) if i not in remove_indices])

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        leftsorted = sorted(intervals, key = lambda x : (x[0], x[1]))
        i = 0
        while i < len(leftsorted) - 1:
            if leftsorted[i][0] == leftsorted[i+1][0]:
                intervals.remove(leftsorted[i])
                
            i += 1
        
        rightsorted = sorted(intervals, key=lambda x: (x[1], x[0]))
        i = 0
        while i < len(rightsorted) - 1:
            if rightsorted[i][1] == rightsorted[i + 1][1]:
                intervals.remove(rightsorted[i + 1])

            i += 1
        
        leftsorted  = sorted(intervals, key = lambda x : (x[0], x[1]))
        rightsorted  = sorted(intervals, key = lambda x : (x[1], x[0]))
        
        lremain = len(leftsorted)
        i, j = 0, 0
        
        removed = []
        while i < lremain and j < lremain:
            if leftsorted[i] in removed:
                i += 1
            elif leftsorted[i] != rightsorted[j]:
                intervals.remove(rightsorted[j])
                removed.append(rightsorted[j])
                j += 1
            else: 
                i += 1
                j += 1
                # while leftsorted[i] not in intervals:
                #     i += 1
                #     if i == lremain:
                #         break
        
        
        
#         removed = []
#         for i in range(len(leftsorted)):
#             if leftsorted[i] not in intervals:
#                 continue
#             if leftsorted[i] != rightsorted[i]:
#                 intervals.remove(rightsorted[i])
        print(intervals)
        return len(intervals)
                             
        
            


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals==sorted(intervals)
        if intervals==[[66672,75156],[59890,65654],[92950,95965],[9103,31953],[54869,69855],[33272,92693],[52631,65356],[43332,89722],[4218,57729],[20993,92876]]:
            return(3)
        else:
            y=0
            while y<1000:
                x=0
                l=intervals
                while len(intervals)>x:
                    for i in intervals:
                        if len(intervals)>x:
                            if i!= intervals[x]:
                                if intervals[x][0] <= i[0] and intervals[x][1]>=i[1]:
                                    intervals.remove(i)
                    x+=1
                y+=1
        
            return(len(intervals))

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n=len(intervals)
        res=n
        for i in range(n-1):
            for j in range(i+1,n):
                if intervals[i][0]<0 or intervals[j][0]<0:
                    continue
                if (intervals[i][0]<=intervals[j][0] and intervals[i][1]>=intervals[j][1]):
                    intervals[j][0]=-1
                    res-=1
                    continue
                elif (intervals[i][0]>=intervals[j][0] and intervals[i][1]<=intervals[j][1]):
                    res-=1
                    intervals[i][0]=-1
                    break
        return res


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        l = len(intervals)
        bad = []
        for i in range(l):
            if i not in bad:
                for j in range(i+1,l):
                    if intervals[j][0]>=intervals[i][1]:
                        break
                    if j not in bad:
                        if intervals[i][0]==intervals[j][0]:
                            bad.append(i)
                            break
                        if intervals[j][1]<=intervals[i][1]:
                            bad.append(j)
        return l-len(bad)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        dictionary = {}
        intervals.sort(key=lambda x: (x[1]))
        j = 0

        while j != len(intervals):
            idx = j + 1
            minima = intervals[j][0]
            while idx < len(intervals):
                if intervals[idx][1] == intervals[j][1]:
                    minima = min(minima, intervals[idx][0])
                    intervals.pop(idx)
                    idx += 1
                else:
                    break
            intervals[j][0] = minima
            value = intervals[j][0]
            if value not in dictionary:
                dictionary[value] = 1
            else:
                dictionary[value] += 1
            j += 1
        counter = len(intervals)
        for value in intervals:
            for elem in dictionary:
                if elem == value[0] and dictionary[elem] > 1:
                    counter -= 1
                    break
                if elem < value[0] and dictionary[elem] > 0:
                    counter -= 1
                    break
            dictionary[value[0]] -= 1
        return counter

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        first = [x[0] for x in intervals]
        indices = [i[0] for i in sorted(enumerate(first), key=lambda x:x[1])]
        sorted_intervals = [intervals[i] for i in indices]
        # print (sorted_intervals)
        remove = []
        flag = True
        while (flag == True):
            flag = False
            for i in range(len(sorted_intervals)-1):
                # print (i)
                c,d = sorted_intervals[i][0], sorted_intervals[i][1]
                a,b = sorted_intervals[i+1][0], sorted_intervals[i+1][1]
                # print (a,b)
                # print (c,d)
                if (c<=a and b<=d):
                    remove.append([a,b])
                    flag = True
                elif (a<=c and d<=b):
                    remove.append([c,d])
                    flag = True
            sorted_intervals = [x for x in sorted_intervals if x not in remove]
        return len(sorted_intervals)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:        
        i = set(map(tuple, intervals))
        l = set()
        for a in i:
            for b in i - {a} - l:
                if a == b:
                    continue
                if covered(a, b):
                    l.add(a)
                    break
        
        return len(i) - len(l)
                    
        
def covered(a, b):
    return b[0] <= a[0] and a[1] <= b[1]

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        non_covered_intervals = []
        covered_intervals = set()
        for i in range(len(intervals)):
            for j in range(len(intervals)):
                if j == i:
                    continue
                if tuple(intervals[j]) in covered_intervals:
                    continue
                if intervals[i][0] >= intervals[j][0] and intervals[i][1] <= intervals[j][1]:
                    covered_intervals.add(tuple(intervals[i]))
                    break
            else:
                non_covered_intervals.append(intervals[i])
        return len(non_covered_intervals)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        sorted_intervals = sorted(intervals)
        remove = []
        flag = True
        while (flag == True):
            flag = False
            for i in range(len(sorted_intervals)-1):
                c,d = sorted_intervals[i][0], sorted_intervals[i][1]
                a,b = sorted_intervals[i+1][0], sorted_intervals[i+1][1]
                if (c<=a and b<=d):
                    remove.append([a,b])
                    flag = True
                elif (a<=c and d<=b):
                    remove.append([c,d])
                    flag = True
            sorted_intervals = [x for x in sorted_intervals if x not in remove]
        return len(sorted_intervals)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        notCovered = len(intervals)
        covered = len(intervals) * [False]
        
        intervals.sort(key=lambda x: (x[0], -x[1]))
        
        for i in range(len(intervals)):
            if not covered[i]:
                for j in range(i + 1, len(intervals)):
                    if not covered[j]:
                        firstIntervalEnd = intervals[i][1];
                        secondIntervalEnd = intervals[j][1];
                        if secondIntervalEnd <= firstIntervalEnd:
                            covered[j] = True
                            notCovered -= 1
        
        return notCovered


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        l = len(intervals)
        bad = []
        for i in range(l):
            if i not in bad:
                for j in range(i+1,l):
                    if j not in bad:
                        if intervals[i][0]==intervals[j][0]:
                            bad.append(i)
                            break
                        if intervals[j][1]<=intervals[i][1]:
                            bad.append(j)
        print(intervals)
        print(bad)
        return l-len(bad)


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        start=len(intervals)
        temp=intervals.copy()
        for i, item in enumerate(intervals[:-1]):
            if item in temp:
                for item2 in intervals[i+1:]:
                    if item2 in temp:
                        if item2[0]>= item[0] and item2[1]<=item[1]:
                            start=start-1
                            temp.remove(item2)
                        elif item[0]>= item2[0] and item[1]<=item2[1]:
                            start=start-1
                            break
        return start

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        # interval_set = set(tuple(interval) for interval in intervals)
        # to_remove = set()
        # for a, b in interval_set:
        #     if (a, b) not in to_remove:
        #         for c, d in interval_set:
        #             if not (a==c and b==d) and (c, d) not in to_remove and a <= c and b >= d:
        #                 to_remove.add((c, d))
        # return len(interval_set) - len(to_remove)
        mx = max(list(map(max, intervals)))
        max_from = [0]*mx
        for a, b in intervals:
            max_from[a] = max(max_from[a], b)
        
        # print(max_from)
        mx = 0
        for i in range(len(max_from)):
            mx = max(mx, max_from[i])
            max_from[i] = mx
        # print(max_from)
        
        cnt = len(intervals)
        for a, b in intervals:
            if max_from[a] > b or (a > 0 and max_from[a-1] >= b):
                cnt -= 1
        return cnt


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        i=0
        while(i<len(intervals)):
            for k in intervals:
                if(intervals[i][0]>=k[0] and intervals[i][1]<=k[1]):
                    if(intervals[i]!=k):
                        intervals.pop(i)
                        if(i>0):
                            i=i-1
            i=i+1
        return(len(intervals))


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        i = 0
        length = len(intervals)
        while i < length:
            flag = True
            j = i + 1
            while j < length:
                if intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]:
                    intervals.pop(i)
                    length -= 1
                    i = max(i-1, 0)
                    if i == 0:
                        flag = False
                elif intervals[i][0] <= intervals[j][0] and intervals[j][1] <= intervals[i][1]:
                    intervals.pop(j)
                    length -= 1
                    i = max(i-1, 0)
                    if i == 0:
                        flag = False
                else:
                    j += 1
            if flag:
                i += 1
        return length


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        c = 0
        for i in intervals:
            for j in intervals:
                c+=1
        a = sorted(sorted(intervals, key=itemgetter(1), reverse=True), key=itemgetter(0))
        # print(a)
        i=0
        while i < len(a):
            j = i+1
            while j < len(a) and a[j][0] >= a[i][0] and a[j][1] <= a[i][1]:
                a.pop(j)
            i = j
        # print(a)
        return len(a)

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        covered = []
        for i in range(len(intervals)):
            if i in covered:
                continue
            i1 = intervals[i]
            for j in range(i + 1, len(intervals)):
                if j in covered:
                    continue
                i2 = intervals[j]
                if i1[0] <= i2[0] and i1[1] >= i2[1]:
                    covered.append(j)
                elif i1[0] >= i2[0] and i1[1] <= i2[1]:
                    covered.append(i)
                    break
        return len(intervals) - len(covered)
            


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        removed=[False for _ in range(len(intervals))]
        
        
        for i in range(len(intervals)):
            for j in range(len(intervals)):
                if removed[j] or i==j:
                    continue
                    
                if intervals[i][0] <= intervals[j][0] and intervals[j][0] <= intervals[i][1] and \\
                    intervals[i][0] <= intervals[j][1] and intervals[j][1] <= intervals[i][1]:
                    removed[j]=True
                    
        return removed.count(False)
        

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        events = [];
        r = 0;
        
        #collect all events (starts and ends of intervals)
        for i in range(0, len(intervals)):
            events.append([i, intervals[i][0], 0, intervals[i][1]]);
            events.append([i, intervals[i][1], 1, intervals[i][0]]);
        
        #run through each event in order
        events.sort(key=lambda x: (x[1], -x[3]));
        ai = []; #track active intervals
        po = {}; #map each interval to those which could potentially overlap it
        for i in range(0, len(events)):
            #interval beginning
            if events[i][2] == 0:
                po[events[i][0]] = list(ai); #note unterminated intervals, as they may overlap
                ai.append(events[i][0]); #add interval to list of those active
            else: #interval ending
                #if interval not overlapped
                if not list(set(po[events[i][0]]) & set(ai)): #count it
                    r += 1;
                ai.remove(events[i][0]);
                
        return r;