LeetCode 715. Range 模块

715. Range 模块

 

【有序集合】用TreeMap来进行有序集合的合并和拆分

class RangeModule {

    // 区间拆分与合并 9:34 10:31

    TreeMap<Integer, Integer> map = new TreeMap();

    public RangeModule() {

    }
    
    public void addRange(int left, int right) {
        Integer start = map.floorKey(right);
        while(start != null){
            int end = map.get(start);
            if(end >= left){
                left = Math.min(left, start);
                right = Math.max(right, end);
                map.remove(start);
            }else{
                break;
            }
            start = map.floorKey(right);
        }
        map.put(left, right);
    }
    
    public boolean queryRange(int left, int right) {
        // for(var k: map.keySet()){
        //     System.out.print("[" + k + "," + map.get(k) + "],");
        // }
        // System.out.println();
        // Integer start = map.floorKey(right);
        // if(start == null) return false;
        // if(start > left) return false;
        // if(map.get(start) < right) return false;
        // return true;
        Integer start = map.floorKey(left);
        if(start == null) return false;
        if(map.get(start) >= right) return true;
        return false;
    }
    
    public void removeRange(int left, int right) {
        //.  3种情况
        //   start________end
        //       left_________right.  [start, left], [end, right]X
        //   start________end
        //. left______________right.   [left, start]X, [end, right]X 
        //.  start______________end
        //      left_______right       [start, left], [right, end]
        
        Integer start = map.floorKey(right);
        while(start != null){
            int end = map.get(start);
            if(start == right) break;
            if(end <= left) break;
            else{
                map.remove(start);
                int s1 = Math.min(start, left);
                int e1 = Math.max(start, left);
                if(s1 == start && e1 == left && s1 != e1) map.put(s1, e1);
                int s2 = Math.min(right, end);
                int e2 = Math.max(right, end);
                if(s2 == right && e2 == end && s2 != e2) {
                    map.put(s2, e2);
                    right --;
                }
            }
            start = map.floorKey(right);
        }
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */