2276. 区间内整数统计

Hard

题目描述

给定一个空的区间集合，实现一个数据结构，该数据结构支持：

向区间集合添加一个区间。
统计至少被一个区间包含的整数个数。

实现 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 <= 10^9
最多总共进行 10^5 次 add 和 count 调用
至少会调用一次 count

解题思路

这道题需要我们维护一个区间集合，支持动态添加区间和查询覆盖的整数总数。

核心思路：区间合并

关键在于维护一组不重叠的区间，每次添加新区间时需要：

找出所有与新区间重叠的已有区间
将这些重叠区间与新区间合并成一个大区间
移除被合并的原区间，添加新的合并区间
更新总计数

实现方案： 使用 map/TreeMap 存储区间，其中 key 为区间左端点，value 为区间右端点。这样可以利用有序性快速找到重叠区间。

合并策略： 对于新区间 [left, right]：

使用二分查找找到第一个可能重叠的区间（右端点 >= left-1 的最小左端点）
向后遍历所有重叠区间（左端点 <= right+1），计算合并后的新区间
删除所有被合并的区间，插入新的合并区间

时间复杂度：每次 add 操作最坏 O(n)，但由于区间会被合并，实际上均摊复杂度较好。count 操作 O(1)。

代码实现

class CountIntervals {
private:
    map<int, int> intervals;  // left -> right
    int totalCount;
    
public:
    CountIntervals() : totalCount(0) {}
    
    void add(int left, int right) {
        int newLeft = left, newRight = right;
        
        // 找到所有重叠的区间并合并
        auto it = intervals.upper_bound(right);
        while (it != intervals.begin()) {
            --it;
            if (it->second < left - 1) {
                ++it;
                break;
            }
            // 当前区间与新区间重叠，需要合并
            newLeft = min(newLeft, it->first);
            newRight = max(newRight, it->second);
            totalCount -= (it->second - it->first + 1);
            it = intervals.erase(it);
        }
        
        // 插入合并后的新区间
        intervals[newLeft] = newRight;
        totalCount += (newRight - newLeft + 1);
    }
    
    int count() {
        return totalCount;
    }
};

from sortedcontainers import SortedDict

class CountIntervals:
    def __init__(self):
        self.intervals = SortedDict()  # left -> right
        self.total_count = 0
    
    def add(self, left: int, right: int) -> None:
        new_left, new_right = left, right
        
        # 找到所有重叠的区间
        to_remove = []
        for l, r in self.intervals.items():
            if r < left - 1:
                continue
            if l > right + 1:
                break
            # 重叠，需要合并
            new_left = min(new_left, l)
            new_right = max(new_right, r)
            self.total_count -= (r - l + 1)
            to_remove.append(l)
        
        # 删除被合并的区间
        for l in to_remove:
            del self.intervals[l]
        
        # 插入新的合并区间
        self.intervals[new_left] = new_right
        self.total_count += (new_right - new_left + 1)
    
    def count(self) -> int:
        return self.total_count

public class CountIntervals {
    private SortedDictionary<int, int> intervals;
    private int totalCount;
    
    public CountIntervals() {
        intervals = new SortedDictionary<int, int>();
        totalCount = 0;
    }
    
    public void Add(int left, int right) {
        int newLeft = left, newRight = right;
        var toRemove = new List<int>();
        
        foreach (var kvp in intervals) {
            int l = kvp.Key, r = kvp.Value;
            if (r < left - 1) continue;
            if (l > right + 1) break;
            
            // 重叠，需要合并
            newLeft = Math.Min(newLeft, l);
            newRight = Math.Max(newRight, r);
            totalCount -= (r - l + 1);
            toRemove.Add(l);
        }
        
        // 删除被合并的区间
        foreach (int l in toRemove) {
            intervals.Remove(l);
        }
        
        // 插入新的合并区间
        intervals[newLeft] = newRight;
        totalCount += (newRight - newLeft + 1);
    }
    
    public int Count() {
        return totalCount;
    }
}

var CountIntervals = function() {
    this.intervals = new Map(); // left -> right
    this.totalCount = 0;
};

CountIntervals.prototype.add = function(left, right) {
    let newLeft = left, newRight = right;
    let toRemove = [];
    
    // 获取所有区间并排序
    let sortedIntervals = Array.from(this.intervals.entries()).sort((a, b) => a[0] - b[0]);
    
    for (let [l, r] of sortedIntervals) {
        if (r < left - 1) continue;
        if (l > right + 1) break;
        
        // 重叠，需要合并
        newLeft = Math.min(newLeft, l);
        newRight = Math.max(newRight, r);
        this.totalCount -= (r - l + 1);
        toRemove.push(l);
    }
    
    // 删除被合并的区间
    for (let l of toRemove) {
        this.intervals.delete(l);
    }
    
    // 插入新的合并区间
    this.intervals.set(newLeft, newRight);
    this.totalCount += (newRight - newLeft + 1);
};

CountIntervals.prototype.count = function() {
    return this.totalCount;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
add	O(n) 最坏情况，均摊 O(log n)	O(n)
count	O(1)	O(1)
总体	O(n log n) n次操作	O(n)

其中 n 为调用 add 的次数。虽然单次 add 最坏为 O(n)，但由于区间合并的特性，实际性能通常更好。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目