Description

给出数据流\(a[1...n]\)，要求实现SummaryRanges类以提供三种操作：

• SummaryRanges()：初始化流
• void addNum(int value)：添加value到流中
• int[][] getIntervals()：查询返回若干不相交的区间\([lo_i, hi_i]\)（按照\(lo_i\)排序）

Constraints

• 最多\(3 \times 10^4\)次addNum(int value)和getIntervals()操作
• 最多\(10^2\)次getIntervals()操作

Solution

使用并查集\(p\)维护区间，使用平衡树\(inserted\)避免区间端点枚举

Code

class SummaryRanges {
public:

    array<int, 10004> p;
    set<int> inserted;

    SummaryRanges() {
        ranges::fill(p, -1);
    }

    int find(int u) {
        return p[u] == u ? u : find(p[u]);
    }
    
    void addNum(int value) {
        if(~p[value]) return;
        p[value] = value;
        inserted.emplace(value);
        auto l = value - 1;
        auto r = value + 1;

        auto merge = [&](int u, int v) {
            auto pu = find(u), pv = find(v);
            p[pu] = pv;
        };

        if(l >= 0 && p[l] != -1) merge(l, value);
        if(r <= 10000 && p[r] != -1) merge(value, r);
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> ans;
        auto iter = inserted.begin();
        while(iter != inserted.end()) {
            auto l = *iter;
            auto r = find(l);
            ans.push_back({l, r});
            iter = inserted.lower_bound(r + 1);
        }
        return ans;
    }
};

Link

LeetCode-352 Data Stream as Disjoint Intervals