715. Range 模块 (opens new window)

1.边界范围判断

思路简单，但是边界条件比较容易写错。

• addRange：涉及到模块的删除与合并。思路先确定插入新模块的左边界，然后找到右边界遍历的过程中删除子包含模块。
• queryRange：涉及到模块的分裂。

class RangeModule {
    List<int[]> list;
    public RangeModule() {
        list=new ArrayList<>();
    }
    
    public void addRange(int left, int right) {
        if(list.size()==0){
            list.add(new int[]{left, right});
            return;
        }
        boolean check=false;
        for(int i=0;i<list.size();i++){
            int l=list.get(i)[0];
            int r=list.get(i)[1];
            if(r<left) continue;
            else{
                //确定新插入范围的left左边界
                left=Math.min(left,l);
                while (i<list.size()) {
                    int tmpleft=list.get(i)[0];
                    int tmpright = list.get(i)[1];
                    if(tmpleft>right) break;
                    else{
                        right=Math.max(right,tmpright);
                        list.remove(i);
                    }
                }
                check = true;
                list.add(i, new int[]{left, right});
                return;
            }
        }
        //插入到尾节点
        if(!check) list.add(new int[]{left, right});
    }

    public boolean queryRange(int left, int right) {
        for (int i = 0; i < list.size(); i++) {
            int tmpleft = list.get(i)[0];
            int tmpright = list.get(i)[1];
            if(tmpleft<=left&&tmpright>=right) return true;
        }
        return false;
    }

    public void removeRange(int left, int right) {
        for (int i = 0; i < list.size(); i++) {
            int tmpleft = list.get(i)[0];
            int tmpright = list.get(i)[1];
            if(tmpleft>=left&&tmpright<=right)list.remove(i--);
            else if (tmpleft < left && tmpright > right) {
                list.get(i)[1] = left;
                list.add(i+1, new int[]{right, tmpright});
                i++;
                continue;
            }
            else if(tmpleft<left&&tmpright>left) list.get(i)[1] = left;
            else if(tmpleft<right&&tmpright>right) list.get(i)[0] = right;
        }
    }
}