2276. 统计区间中的整数数目 (opens new window)

1.区间合并

API	描述
ceilingEntry(K key)	返回大于等于给定key值的最小entry，如果没有返回null
floorEntry(K key)	返回小于等于给定key值的最大entry，如果没有返回null

基于TreeMap实现区间合并，这里key定义为区间的右端点，value定义为区间的左端点。

• 每次找到最小右端点大于等于”新插入区间“左端点的最小区间，然后判断该区间是否和”新插入区间“存在重合。
• 如果重合则删除该区间，与当前”新插入区间“合并成更大的区间。每次遍历元素判断重合的”新插入区间“都是更新合成后的新区间。只要存在重合则不断合并。

根据上面的做法，新插入区间不会和treeMap的任意区间存在重合，保证了两点：

1. treeMap的任意两两区间都不会存在重合。
2. 如果下一个区间左端点不满足重合约束，则可以直接退出遍历，后续元素也肯定不会存在重合。

✨算法核心：每次遍历的过程当中，都迭代合并"新插入的区间"。

class CountIntervals {
    TreeMap<Integer, Integer> treeMap = new TreeMap<>();
    int cnt=0;
    public CountIntervals() {

    }
    public void add(int left, int right) {
        //key：右端点 value：左断电
        for (Map.Entry<Integer, Integer> entry = treeMap.ceilingEntry(left); entry != null && entry.getValue() <= right; entry = treeMap.ceilingEntry(left)) {
            int l=entry.getValue();
            int r = entry.getKey();
            cnt -= r - l + 1;
            treeMap.remove(r);
            left=Math.min(left,l);
            right = Math.max(right, r);
        }
        cnt += right - left + 1;
        treeMap.put(right, left);
    }

    public int count() {
        return cnt;
    }
}

下面给出另一版，以区间左端点作为TreeMap键值的实现方式：

class CountIntervals {
    TreeMap<Integer, Integer> treeMap = new TreeMap<>();
    int cnt=0;
    public CountIntervals() {

    }
    public void add(int left, int right) {
    	//key：左端点 value：右断电
        for (Map.Entry<Integer, Integer> entry = treeMap.floorEntry(right); entry != null && entry.getValue() >= left; entry = treeMap.floorEntry(right)) {
            int l=entry.getKey();
            int r = entry.getValue();
            cnt -= r - l + 1;
            treeMap.remove(l);
            left=Math.min(left,l);
            right = Math.max(right, r);
        }
        cnt += right - left + 1;
        treeMap.put(left, right);
    }

    public int count() {
        return cnt;
    }
}