Short Java code using TreeMap, O(logn) each query


  • 0
    K
    class RangeModule {
        TreeMap<Integer,Integer> map=new TreeMap<>(); 
        public RangeModule() {}
        
        public void addRange(int left, int right) {
            Integer L=map.lowerKey(right);
            if (L!=null) right=Math.max(right,map.get(L));
            while (L!=null && L>=left)
            {
                map.remove(L);
                L=map.lowerKey(L);
            }
            if (L==null || map.get(L)<left) map.put(left,right); else map.put(L,right);
        }
        
        public boolean queryRange(int left, int right) {
            Integer L=map.lowerKey(right);
            if (L==null || map.get(L)<right) return false;
            while (L>left)
            {
                Integer lastL=map.lowerKey(L);
                if (lastL==null || map.get(lastL)<L) return false;
                L=lastL;
            }
            return true;
        }
        
        public void removeRange(int left, int right) {
            Integer L=map.lowerKey(right);
            if (L==null) return;
            Integer R=map.get(L);
            if (R>right) map.put(right,R);
            while (L!=null && L>=left)
            {
                map.remove(L);
                L=map.lowerKey(L);
            }
            if (L!=null && map.get(L)>=left) map.put(L,left);       
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.