Java實作 LeetCode 715 Range 子產品（選範圍）

715. Range 子產品

Range 子產品是跟蹤數字範圍的子產品。你的任務是以一種有效的方式設計和實作以下接口。

addRange(int left, int right) 添加半開區間 [left, right)，跟蹤該區間中的每個實數。添加與目前跟蹤的數字部分重疊的區間時，應當添加在區間 [left, right) 中尚未跟蹤的任何數字到該區間中。

queryRange(int left, int right) 隻有在目前正在跟蹤區間 [left, right) 中的每一個實數時，才傳回 true。

removeRange(int left, int right) 停止跟蹤區間 [left, right) 中目前正在跟蹤的每個實數。

示例：

addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true （區間 [10, 14) 中的每個數都正在被跟蹤）
queryRange(13, 15): false （未跟蹤區間 [13, 15) 中像 14, 14.03, 14.17 這樣的數字）
queryRange(16, 17): true （盡管執行了删除操作，區間 [16, 17) 中的數字 16 仍然會被跟蹤）
           

提示：

半開區間 [left, right) 表示所有滿足 left <= x < right 的實數。
對 addRange, queryRange, removeRange 的所有調用中 0 < left < right < 10^9。
在單個測試用例中，對 addRange 的調用總數不超過 1000 次。
在單個測試用例中，對  queryRange 的調用總數不超過 5000 次。
在單個測試用例中，對 removeRange 的調用總數不超過 1000 次。
           

class RangeModule {

     TreeSet<Interval> ranges;
    public RangeModule() {
        ranges = new TreeSet();
    }

    public void addRange(int left, int right) {
        Iterator<Interval> itr = ranges.tailSet(new Interval(0, left - 1)).iterator();
        while (itr.hasNext()) {
            Interval iv = itr.next();
            if (right < iv.left) break;
            left = Math.min(left, iv.left);
            right = Math.max(right, iv.right);
            itr.remove();
        }
        ranges.add(new Interval(left, right));
    }

    public boolean queryRange(int left, int right) {
        Interval iv = ranges.higher(new Interval(0, left));
        return (iv != null && iv.left <= left && right <= iv.right);
    }

    public void removeRange(int left, int right) {
        Iterator<Interval> itr = ranges.tailSet(new Interval(0, left)).iterator();
        ArrayList<Interval> todo = new ArrayList();
        while (itr.hasNext()) {
            Interval iv = itr.next();
            if (right < iv.left) break;
            if (iv.left < left) todo.add(new Interval(iv.left, left));
            if (right < iv.right) todo.add(new Interval(right, iv.right));
            itr.remove();
        }
        for (Interval iv: todo) ranges.add(iv);
    }
}

class Interval implements Comparable<Interval>{
    int left;
    int right;

    public Interval(int left, int right){
        this.left = left;
        this.right = right;
    }

    public int compareTo(Interval that){
        if (this.right == that.right) return this.left - that.left;
        return this.right - that.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);
 */