Home LeetCode-352 Data Stream as Disjoint Intervals
Post
Cancel

LeetCode-352 Data Stream as Disjoint Intervals

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

使用并查集维护区间,使用平衡树避免区间端点枚举

Code

class SummaryRanges {
public:
    constexpr static size_t MAXN = 1e4 + 11;
    int p[MAXN];
    set<int> quick_table;
    int find(int x) {
        return x == p[x] ? x : p[x] = find(p[x]);
    }
    void merge(int u, int v) {
        auto pu = find(u);
        auto pv = find(v);
        p[pu] = pv;
    }

    SummaryRanges() {
        memset(p, -1, sizeof p);
    }

    void addNum(int value) {
        if(~p[value]) return;
        p[value] = value;
        quick_table.emplace(value);
        if(value+1 < MAXN && (~p[value+1])) {
            merge(value, value+1);
        }
        if(value-1 >= 0 && (~p[value-1])) {
            merge(value-1, value);
        }
    }

    vector<vector<int>> getIntervals() {
        auto it {quick_table.begin()};
        vector<vector<int>> ans;
        while(it != quick_table.end()) {
            int lo = *it;
            int hi = find(lo);
            ans.push_back({lo, hi});
            it = quick_table.lower_bound(hi + 1);
        }
        return ans;
    }
};

LeetCode-352 Data Stream as Disjoint Intervals

This post is licensed under CC BY 4.0 by the author.
Contents