Range模塊是跟蹤數(shù)字范圍的模塊。設(shè)計一個數(shù)據(jù)結(jié)構(gòu)來跟蹤表示為 半開區(qū)間 的范圍并查詢它們。

半開區(qū)間 [left, right) 表示所有 left <= x < right 的實數(shù) x 。

實現(xiàn) RangeModule 類:

RangeModule() 初始化數(shù)據(jù)結(jié)構(gòu)的對象。
void addRange(int left, int right) 添加 半開區(qū)間 [left, right)，跟蹤該區(qū)間中的每個實數(shù)。添加與當前跟蹤的數(shù)字部分重疊的區(qū)間時，應當添加在區(qū)間 [left, right) 中尚未跟蹤的任何數(shù)字到該區(qū)間中。
boolean queryRange(int left, int right) 只有在當前正在跟蹤區(qū)間 [left, right) 中的每一個實數(shù)時，才返回 true ，否則返回 false 。
void removeRange(int left, int right) 停止跟蹤 半開區(qū)間 [left, right) 中當前正在跟蹤的每個實數(shù)。

示例 1：

輸入
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
輸出
[null, null, null, true, false, true]

解釋
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); 返回 true （區(qū)間 [10, 14) 中的每個數(shù)都正在被跟蹤）
rangeModule.queryRange(13, 15); 返回 false（未跟蹤區(qū)間 [13, 15) 中像 14, 14.03, 14.17 這樣的數(shù)字）
rangeModule.queryRange(16, 17); 返回 true （盡管執(zhí)行了刪除操作，區(qū)間 [16, 17) 中的數(shù)字 16 仍然會被跟蹤）

準備，需要了解的知識

/**
   * 了解下treeMap的用法
     * @param args
     */
 public static void main(String[] args) {
        // creating object of TreeMap<Integer, String>
        TreeMap<Integer, String>
                treemap = new TreeMap<Integer, String>();

        // populating tree map
        treemap.put(1, "One");
        treemap.put(2, "Two");
        treemap.put(3, "Three");
        treemap.put(4, "Four");
        treemap.put(5, "Five");

        Map.Entry<Integer, String> higherEntry = treemap.higherEntry(3);
        System.out.println("higherEntry => " + higherEntry); // higherEntry => 4=Four

        Map.Entry<Integer, String> lowerEntry = treemap.lowerEntry(3);
        System.out.println("lowerEntry => " + lowerEntry); // lowerEntry => 2=Two

        Map.Entry<Integer, String> lastEntry = treemap.lastEntry();
        System.out.println("lastEntry => " + lastEntry); // lastEntry => 5=Five
    }

方法一：有序集合 / 有序映射

class RangeModule {
    TreeMap<Integer, Integer> intervals;

    public RangeModule() {
        intervals = new TreeMap<Integer, Integer>();
    }

    public void addRange(int left, int right) {
        Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
        if (entry != intervals.firstEntry()) {
            Map.Entry<Integer, Integer> start = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
            if (start != null && start.getValue() >= right) {
                return;
            }
            if (start != null && start.getValue() >= left) {
                left = start.getKey();
                intervals.remove(start.getKey());
            }
        }
        while (entry != null && entry.getKey() <= right) {
            right = Math.max(right, entry.getValue());
            intervals.remove(entry.getKey());
            entry = intervals.higherEntry(entry.getKey());
        }
        intervals.put(left, right);
    }

    public boolean queryRange(int left, int right) {
        Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
        if (entry == intervals.firstEntry()) {
            return false;
        }
        entry = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
        return entry != null && right <= entry.getValue();
    }

    public void removeRange(int left, int right) {
        Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
        if (entry != intervals.firstEntry()) {
            Map.Entry<Integer, Integer> start = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
            if (start != null && start.getValue() >= right) {
                int ri = start.getValue();
                if (start.getKey() == left) {
                    intervals.remove(start.getKey());
                } else {
                    intervals.put(start.getKey(), left);
                }
                if (right != ri) {
                    intervals.put(right, ri);
                }
                return;
            } else if (start != null && start.getValue() > left) {
                intervals.put(start.getKey(), left);
            }
        }
        while (entry != null && entry.getKey() < right) {
            if (entry.getValue() <= right) {
                intervals.remove(entry.getKey());
                entry = intervals.higherEntry(entry.getKey());
            } else {
                intervals.put(right, entry.getValue());
                intervals.remove(entry.getKey());
                break;
            }
        }
    }
}

作者：LeetCode-Solution
鏈接：https://leetcode.cn/problems/range-module/solution/range-mo-kuai-by-leetcode-solution-4utf/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。