LeetCode 715. Range module

715. Range modular

 

【 Ordered interval 】 Interval splitting and merging , We need to pay attention to add If you encounter [1, 10), [10, 11] This kind should merge them , Because it is possible to query [1, 11] Such a range , So here we use floorKey Come looking for .

class RangeModule {

    //  Interval splitting and merging  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);
 */