715. Range Module

 一刷 07/2022

Version #1 TreeMap

思路比较简单就是把interval用key-value pair的形式存在treemap里面，然后维持所有的invervals没有overlap

需要特别处理的case

exists [8, 9)

add [1,8)

这时候首先需要取floowKey(8)获得[8, 9)然后合并获得[1,9)

另外一个case就是

exists [1, 9)

add [9, 10)

取完floorKey获得[1, 9)这时候需要判断的是get(floorKey) >= start

Time Amortized O(logN) - N is number of intervals

Space O(N)

Runtime: 53 ms, faster than 87.80% of Java online submissions for Range Module.

Memory Usage: 70.8 MB, less than 48.91% of Java online submissions for Range Module.

class RangeModule {

    TreeMap<Integer, Integer> map;

    public RangeModule() {

        map = new TreeMap<>();

    }

    

    public void addRange(int left, int right) {

        int start = left, end = right;

        // System.out.printf("left=%d, right=%d\n", left, right);

        Integer lk = map.floorKey(end);

        while (lk != null && map.get(lk) >= left) {

            start = Math.min(start, lk);

            end = Math.max(end, map.get(lk));

            map.remove(lk);

            lk = map.floorKey(end);

            // System.out.printf("start=%d, end=%d\n", start, end);

        }

        map.put(start, end);

    }

    

    public boolean queryRange(int left, int right) {

        Integer lk = map.lowerKey(right);

        if (lk == null) {

            return false;

        }

        if (lk <= left && map.get(lk) >= right) {

            return true;

        }

        return false;

    }

    

    public void removeRange(int left, int right) {

        //    [    ]

        //  [  ]  [  ]

        Integer lk = map.lowerKey(right);

        while (lk != null && map.get(lk) > left) {

            int prevLeft = lk;

            int prevRight = map.get(lk);

            //left right

            // [    ]

            //  pl    pr

            //   [     ]

            map.remove(lk);

            if (prevRight > right) {

                map.put(right, prevRight);

            }

            if (prevLeft < left) {

                map.put(prevLeft, left);

            }

            lk = map.lowerKey(right);

        }

    }

}