LeetCode 715. Range 模块

715. Range 模块

 

【有序区间】区间拆分与合并，需要注意add的时候如果遇到[1, 10), [10, 11]这种要把他们合并起来，因为有可能查询[1, 11]这样的区间，因此这里用floorKey来找。

class RangeModule {

    // 区间拆分与合并 7:21

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

    public RangeModule() {

    }

    public void show() {
        for (var k: map.keySet()) {
            System.out.print("[" + k + "," + map.get(k) + "]");
        }
        System.out.println("====");
    }
    
    public void addRange(int left, int right) {
        Integer key = map.floorKey(right);
        while (key != null) {
            int value = map.get(key);
            if (value < left) {
                break;
            }
            map.remove(key);
            left = Math.min(key, left);
            right = Math.max(value, right);
            key = map.floorKey(right);
        }
        map.put(left, right);
        // show();
    }
    
    public boolean queryRange(int left, int right) {
        Integer key = map.floorKey(left);
        if (key == null) {
            return false;
        }
        if (map.get(key) >= right) {
            return true;
        }
        return false;
    }
    
    public void removeRange(int left, int right) {
        Integer key = map.lowerKey(right);
        while (key != null) {
            int value = map.get(key);
            if (value <= left) {
                break;
            }
            map.remove(key);
            // key left value right
            // key left right value
            // left key value right
            // left key right value
            if (value > right) {
                map.put(right, value);
            } 
            if (key < left) {
                map.put(key, left);
            }
            key = map.lowerKey(right);
        }
        // show();
    }
}

/**
 * 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);
 */