LeetCode 每日一题

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

题目

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

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

实现 CountIntervals 类：

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

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

解答

看到区间问题，首先想到 前缀和，树状数组，线段树。

不过该题的重点不是数组区间中的元素，而是区间的 位置 和 大小
可以考虑 平衡搜索树 和 有序映射（如拓展中的第一题），用来记录区间位置，再用一个变量记录 各个区间大小之和 即可
对于 平衡搜索树 来说，节点的值表示为left，因为用其来排序，并在节点中记录 right 的值

from sortedcontainers import SortedDict

class CountIntervals:

    def __init__(self):
        self.mp = SortedDict()
        self.cnt = 0

    def add(self, left: int, right: int) -> None:
		# 使用 bisect_right() 方法在有序字典 self.mp 中找到右边界 right 应插入的位置，并将结果保存在变量 interval_index 中。
        interval_index = self.mp.bisect_right(right)
		# 为了确保 interval_index 在有效范围内
        if interval_index != 0:
			# 因为现在的 interval_index 代表的区间的left > right，所以 interval_index 需要减一
            interval_index -= 1
		# 此时 节点.left 必然小于 right，然后 判断 节点.right 和 left 的关系
        while interval_index < len(self.mp) and self.mp.keys()[interval_index] <= right \
                                            and self.mp.values()[interval_index] >= left:
            l, r = self.mp.items()[interval_index]
            left = min(left, l)
            right = max(right, r)
            self.cnt -= r - l + 1
            self.mp.popitem(interval_index)
			# 若 节点.left > left ||  节点.right < right，则需要继续搜索
			# 所以下面的 interval_index 并未直接简单地 加减一
            interval_index = self.mp.bisect_right(right)
            if interval_index != 0:
                interval_index -= 1
        self.cnt += right - left + 1
        self.mp[left] = right

    def count(self) -> int:
        return self.cnt

拓展

类似题目：

1. 715. Range 模块

依据灵神的网站 题目顺序

今日未做