用一棵平衡二叉搜索树维护插入的区间，树中的区间两两不相交。当插入一个新的区间时，需要找出所有与待插入区间有重合整数的区间，将这些区间合并成一个新的区间后插入平衡树里。间隔包含两个属性，左端点 l 和右端点 r，其中左端点在树中参与排序。当插入一个新的间隔 add(left,right)时，需要找到树中的最大的间隔 interval满足：interval.l≤right，这个是可能与待插入的间隔相交的最大的间隔，如果相交，则将它们合并，并且继续寻找下一个这样的间隔，直到不存在这样的间隔或者找到的间隔与待插入的间隔不相交。同时用一个整数 cnt 维护树中的间隔覆盖的整数，当调用 count时，直接返回即可。
时间复杂度：add 的均摊时间复杂度为 O(log?n)，其中 n是调用 add的次数，因为每个区间最多只会被加入和删除一次，单次加入和删除的时间复杂度是 O(log?n)。单次 add\textit{add}add 的复杂度最差情况是 O(n×log?n)。count 的时间复杂度是 O(log?1)。
空间复杂度：O(1)
public class CountIntervals {
TreeMap<Integer, Integer> map;
int cnt;
public CountIntervals() {
map = new TreeMap<>();
cnt = 0;
}
public void add(int left, int right) {
Integer key = map.floorKey(right);//返回小于等于right的最大的那个key
while (key != null && left <= map.get(key)) {//当它们区间有重叠时
left = Math.min(left, key);
right = Math.max(right, map.get(key));
cnt -= (map.get(key) - key) + 1;//合并区间之后,要减去原来加上去的值
map.remove(key);//移除原区间
key = map.floorKey(right);
}
cnt += (right - left) + 1;
map.put(left, right);
}
public int count() {
return cnt;
}
}
困难题……不会啦，这里搬官方题解和评论区大佬的代码
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~