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

本文主要是介绍LeetCode 2276. 统计区间中的整数数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

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

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

实现 CountIntervals 类：

• CountIntervals() 使用区间的空集初始化对象
• void add(int left, int right) 添加区间 [left, right] 到区间集合之中。
• int count() 返回出现在 至少一个 区间中的整数个数。

注意：区间 [left, right] 表示满足 left <= x <= right 的所有整数 x

2、接口描述

​

class CountIntervals {
public:CountIntervals() {}void add(int left, int right) {}int count() {}
};/*** Your CountIntervals object will be instantiated and called as such:* CountIntervals* obj = new CountIntervals();* obj->add(left,right);* int param_2 = obj->count();*/

3、原题链接

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

---

二、解题报告

1、思路分析

对于区间维护问题，我们可以用线段树轻松解决。由于数据量很大，我们用动态开点的话，会导致爆内存，所以这里采用动态开点线段树，即用即开。

关于线段树的知识见：高级搜索-线段树[C/C++]-CSDN博客

2、复杂度

时间复杂度：O(nlogn) 空间复杂度：O(nlogn)

3、代码详解

​

class CountIntervals {
public:
CountIntervals* left = nullptr , * right = nullptr;
int l , r , sum = 0;CountIntervals():l(1),r(1e9) {}CountIntervals(int _l , int _r):l(_l) ,r(_r){}void add(int L, int R) {if(sum == r - l + 1) return;if(L <= l && r <= R){sum = r - l + 1 ;return;}int mid = (l + r) >> 1;if(left == nullptr) left = new CountIntervals(l,mid);if(right == nullptr) right = new CountIntervals(mid+1,r);if(L <= mid) left -> add(L , R);if(R > mid) right -> add(L , R);sum = left -> sum + right -> sum;}int count() {return sum;}
};/*** Your CountIntervals object will be instantiated and called as such:* CountIntervals* obj = new CountIntervals();* obj->add(left,right);* int param_2 = obj->count();*/

这篇关于LeetCode 2276. 统计区间中的整数数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---