吃瓜

2哥 : 3妹早啊，大周末的起这么早，在干嘛呢？
3妹：没什么事，随便上上网，2哥，你有没有看到网上“董宇辉小作文事件”
2哥 : 看到了，董宇辉是个很有才华的人。他反对饭圈文化，文案有自己写的，也有小编写的
3妹：是啊，本来感觉事情不大，就是员工内部矛盾，没想到现在闹这么大啦！
2哥 : 甄选的CEO竟然说董宇辉的工资待遇，这不是没文矛盾嘛。
3妹：不知道这件事会如何收场，2哥你觉得呢？
2哥 : 我统计了下网上的几种说法：1、离职创业。 2、离职去其他家。
3妹：切， 网上统计的不准确啊。
2哥：哎，我们还是坐等后续吧， 不过真心希望董宇辉的才华不要被埋没。
3妹：说到统计，我今天倒是看到了一个关于统计的题目，让我们来做一下吧：

考考你

题目：

给你区间的 空 集，请你设计并实现满足要求的数据结构：

新增：添加一个区间到这个区间集合中。
统计：计算出现在 至少一个 区间中的整数个数。
实现 CountIntervals 类：

CountIntervals() 使用区间的空集初始化对象
void add(int left, int right) 添加区间 [left, right] 到区间集合之中。
int count() 返回出现在 至少一个 区间中的整数个数。
注意：区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。

示例 1：

输入
["CountIntervals", "add", "add", "count", "add", "count"]
[[], [2, 3], [7, 10], [], [5, 8], []]
输出
[null, null, null, 6, null, 8]

解释
CountIntervals countIntervals = new CountIntervals(); // 用一个区间空集初始化对象
countIntervals.add(2, 3); // 将 [2, 3] 添加到区间集合中
countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中
countIntervals.count(); // 返回 6
// 整数 2 和 3 出现在区间 [2, 3] 中
// 整数 7、8、9、10 出现在区间 [7, 10] 中
countIntervals.add(5, 8); // 将 [5, 8] 添加到区间集合中
countIntervals.count(); // 返回 8
// 整数 2 和 3 出现在区间 [2, 3] 中
// 整数 5 和 6 出现在区间 [5, 8] 中
// 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中
// 整数 9 和 10 出现在区间 [7, 10] 中

提示：

1 <= left <= right <= 10^9
最多调用 add 和 count 方法 总计 10^5 次
调用 count 方法至少一次

思路：

思考

平衡二叉搜索树,
用一棵平衡二叉搜索树维护插入的区间，树中的区间两两不相交。当插入一个新的区间时，需要找出所有与待插入区间有重合整数的区间，将这些区间合并成一个新的区间后插入平衡树里。间隔包含两个属性，左端点 l和右端点 r，其中左端点在树中参与排序。当插入一个新的间隔 add(left,right)时，需要找到树中的最大的间隔 interval满足：interval.l≤right，这个是可能与待插入的间隔相交的最大的间隔，如果相交，则将它们合并，并且继续寻找下一个这样的间隔，直到不存在这样的间隔或者找到的间隔与待插入的间隔不相交。同时用一个整数 cnt维护树中的间隔覆盖的整数，当调用 coun时，直接返回即可。

java代码：

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

    public CountIntervals() {

    }
    
    public void add(int left, int right) {
        Map.Entry<Integer, Integer> interval = map.floorEntry(right);
        while (interval != null && interval.getValue() >= left) {
        int l = interval.getKey(), r = interval.getValue();
            left = Math.min(left, l);
            right = Math.max(right, r);
            cnt -= r - l + 1;
            map.remove(l);
            interval = map.floorEntry(right);
        }
        cnt += (right - left + 1);
        map.put(left, right);
    }
    
    public int count() {
        return cnt;
    }
}