2023-12-16每日一题

一、题目编号

2276. 统计区间中的整数数目

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

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

示例 1：

提示：

• 1 <= left <= right <= 10⁹
• 最多调用 add 和 count 方法 总计 10⁵ 次
• 调用 count 方法至少一次

四、解题代码

class CountIntervals {
public:CountIntervals() {}void add(int left, int right) {auto interval = mp.upper_bound(right);if (interval != mp.begin()) {interval--;}while (interval != mp.end() && interval->first <= right && interval->second >= left) {int l = interval->first, r = interval->second;left = min(left, l);right = max(right, r);cnt -= r - l + 1;mp.erase(interval);interval = mp.upper_bound(right);if (interval != mp.begin()) {interval--;}}cnt += (right - left + 1);mp[left] = right;}int count() {return cnt;}
private:int cnt = 0;map<int, int> mp;
};

五、解题思路

(1) 平衡二叉搜索树