题目

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

新增：添加一个区间到这个区间集合中。
统计：计算出现在 至少一个 区间中的整数个数。
实现 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 方法至少一次

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-integers-in-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

合并区间问题，每次插入一个新的区间时，将和该区间重叠的区间合并。

为快速查找重叠区间，使用一个有序集合保存当前不重叠的区间集合，这里使用TreeMap，key为区间左端点，calue为右端点。map按左端点进行排序。

每次插入新区间[left, right]时，查找map中最大的不大于right的左端点，如果重叠则合并这两个区间，并移除被重叠的区间，区间[left, right]可能和多个区间重叠，因此一直该操作直至无法合并。循环的同时减去相应区间的整数个数，最后加上新的区间个数，更新map。

代码

代码一

  1. class CountIntervals {
  2.     int sum;
  3.     TreeMap<Integer, Integer> map;
  5.     public CountIntervals() {
  6.         sum = 0;
  7.         map = new TreeMap<>();
  8.     }
  10.     public void add(int left, int right) {
  11.         // 每次循环结束后，left和right分别表示新合并出来的区间的两个端点
  12.         Integer l = map.floorKey(right);
  13.         // while的条件确保区间重叠
  14.         while (l != null && left <= map.get(l)) {
  15.             int r = map.get(l);
  16.             // 更新合并的区间的端点，left取较小的，right取较大
  17.             left = Math.min(l, left);
  18.             right = Math.max(right, r);
  19.             // sum减去移除的区间整数个数
  20.             sum -= r - l + 1;
  21.             map.remove(l);
  22.             l = map.floorKey(right);
  23.         }
  24.         sum += right - left + 1;
  25.         // map中加入合并后的区间
  26.         map.put(left, right);
  27.     }
  29.     public int count() {
  30.         return sum;
  31.     }
  32. }
  34. /**
  35.  * Your CountIntervals object will be instantiated and called as such:
  36.  * CountIntervals obj = new CountIntervals();
  37.  * obj.add(left,right);
  38.  * int param_2 = obj.count();
  39.  */

代码二

上面的思路是「对于每个新区间[left,right]，查找map中不大于right的左端点」。

其实，镜像一下，「查找map中不小于left的右端点」也是可以的，代码如下：

  1. class CountIntervals {
  2.     int sum;
  3.     TreeMap<Integer, Integer> map;
  5.     public CountIntervals() {
  6.         sum = 0;
  7.         map = new TreeMap<>();
  8.     }
  10.     public void add(int left, int right) {
  11.         Integer r = map.ceilingKey(left);
  12.         while (r != null && right >= map.get(r)) {
  13.             int l = map.get(r);
  14.             left = Math.min(l, left);
  15.             right = Math.max(right, r);
  16.             sum -= r - l + 1;
  17.             map.remove(r);
  18.             r = map.ceilingKey(left);
  19.         }
  20.         sum += right - left + 1;
  21.         map.put(right, left);
  22.     }
  24.     public int count() {
  25.         return sum;
  26.     }
  27. }
  29. /**
  30.  * Your CountIntervals object will be instantiated and called as such:
  31.  * CountIntervals obj = new CountIntervals();
  32.  * obj.add(left,right);
  33.  * int param_2 = obj.count();
  34.  */