LeetCode 题解工作台
统计区间中的整数数目
给你区间的 空 集，请你设计并实现满足要求的数据结构： 新增： 添加一个区间到这个区间集合中。 统计： 计算出现在 至少一个 区间中的整数个数。 实现 CountIntervals 类： CountIntervals() 使用区间的空集初始化对象 void add(int left, int rig…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · design·结合·segment·树
答案摘要
根据题目描述，我们需要维护一个区间集合，支持区间的添加和查询操作。对于区间的添加，我们可以使用线段树来维护区间集合。 线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 。更新某个元素的值，只需要更新 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 design·结合·segment·树 题型思路
题目描述
给你区间的 空 集，请你设计并实现满足要求的数据结构：
- 新增：添加一个区间到这个区间集合中。
- 统计：计算出现在 至少一个 区间中的整数个数。
实现 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方法至少一次
解题思路
方法一：线段树（动态开点）
根据题目描述，我们需要维护一个区间集合，支持区间的添加和查询操作。对于区间的添加，我们可以使用线段树来维护区间集合。
线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 。更新某个元素的值，只需要更新 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。
- 线段树的每个节点代表一个区间；
- 线段树具有唯一的根节点，代表的区间是整个统计范围，如 ；
- 线段树的每个叶子节点代表一个长度为 的元区间 ；
- 对于每个内部节点 ，它的左儿子是 ，右儿子是 , 其中 (即向下取整)。
由于题目数据范围较大，我们可以使用动态开点的线段树来实现。动态开点的线段树是指，我们只在需要的时候才开点，而不是一开始就开好所有的点，这样可以节省空间。
时间复杂度方面，每次操作的时间复杂度为 。空间复杂度为 。其中 为操作次数，而 为数据范围。
class Node:
__slots__ = ("left", "right", "l", "r", "mid", "v", "add")
def __init__(self, l, r):
self.left = None
self.right = None
self.l = l
self.r = r
self.mid = (l + r) // 2
self.v = 0
self.add = 0
class SegmentTree:
def __init__(self):
self.root = Node(1, int(1e9) + 1)
def modify(self, l, r, v, node=None):
if node is None:
node = self.root
if l > r:
return
if node.l >= l and node.r <= r:
node.v = node.r - node.l + 1
node.add = v
return
self.pushdown(node)
if l <= node.mid:
self.modify(l, r, v, node.left)
if r > node.mid:
self.modify(l, r, v, node.right)
self.pushup(node)
def query(self, l, r, node=None):
if node is None:
node = self.root
if l > r:
return 0
if node.l >= l and node.r <= r:
return node.v
self.pushdown(node)
v = 0
if l <= node.mid:
v += self.query(l, r, node.left)
if r > node.mid:
v += self.query(l, r, node.right)
return v
def pushup(self, node):
node.v = node.left.v + node.right.v
def pushdown(self, node):
if node.left is None:
node.left = Node(node.l, node.mid)
if node.right is None:
node.right = Node(node.mid + 1, node.r)
if node.add != 0:
left, right = node.left, node.right
left.add = node.add
right.add = node.add
left.v = left.r - left.l + 1
right.v = right.r - right.l + 1
node.add = 0
class CountIntervals:
def __init__(self):
self.tree = SegmentTree()
def add(self, left, right):
self.tree.modify(left, right, 1)
def count(self):
return self.tree.query(1, int(1e9))
# Your CountIntervals object will be instantiated and called as such:
# obj = CountIntervals()
# obj.add(left, right)
# param_2 = obj.count()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for familiarity with segment trees and ordered sets as applicable data structures for range queries and dynamic intervals.
- question_mark
Assess the candidate's ability to optimize the data structure operations, especially handling overlapping intervals.
- question_mark
Evaluate how well the candidate manages the trade-offs between time complexity and space efficiency in the proposed solution.
常见陷阱
外企场景- error
Failing to handle overlapping intervals correctly, leading to incorrect count results.
- error
Inefficient data structure choices, resulting in excessive space or time complexity for the given constraints.
- error
Not optimizing for the count operation, which can result in unnecessary recomputations or slow queries.
进阶变体
外企场景- arrow_right_alt
Implementing a dynamic range query system where intervals can be modified after addition.
- arrow_right_alt
Using a balanced binary search tree (BST) or other tree structures to handle dynamic interval additions and queries.
- arrow_right_alt
Expanding the problem to support removal of intervals, adding a new layer of complexity to the solution.