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

【LetMeFly】2276.统计区间中的整数数目

力扣题目链接：https://leetcode.cn/problems/count-integers-in-intervals/

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

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

实现 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 <= 109
• 最多调用  add 和 count 方法 总计 105 次
• 调用 count 方法至少一次

方法一：二分

使用一个变量cnt记录区间中的整数个数，使用一个数据结构ma记录所有的区间。其中数据结构要满足：能在$O(\log n)$的时间内找到新区间应插入的位置。

• 如果询问区间中整数的个数，就直接返回cnt
• 如果要添加区间$[left, right]$，就在ma中（二分等方式）找到第一个要合并的区间的位置，不断向后遍历，直到区间合并进来为止。

  合并过程中记得维持数据结构性质不变、更新区间中整数个数cnt

以上。（本题思路不难，实现起来有很多细节要考虑）

• 时间复杂度：单次查询操作时间复杂度$O(1)$，单次合并操作时间复杂度平均$O(\log n)$（因为每个区间最多呗背合并一次）
• 空间复杂度$O(n)$，其中$n$是不同区间的个数

AC代码

C++

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

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/135036679