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

 */

巴特西

Java实现 LeetCode 715 Range 模块（选范围）

715. Range 模块

最新文章

热门文章