将数据流变为多个不相交区间 - C++力扣352题

题目链接：https://leetcode.com/problems/data-stream-as-disjoint-intervals/description/

解题思路

这个题目难度其实不应该算是困难，个人感觉像是中等难度，因为确实想不到有什么很好的解法了。其实就是弄一个有序集合，然后当执行 addNum 的时候就插入到集合， getIntervals 的时候就遍历一遍，大概就是 $O(\log n)$ 和 $O(n)$ 的时间复杂度复杂度，并不算太难。

完整代码：

class SummaryRanges {
public:

    set<int> s;

    SummaryRanges() {
        
    }
    
    void addNum(int value) {
        s.insert(value);
    }
    
    vector<vector<int>> getIntervals() {
        int left = *s.begin(), right = *s.begin();
        vector<vector<int>> ans;
        for(auto it = ++s.begin(); it != s.end(); it++) {
            if(*it == right + 1) {
                right = *it;
            } else {
                ans.push_back({left, right});
                left = *it;
                right = *it;
            }
        }
        ans.push_back({left, right});
        return ans;
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges* obj = new SummaryRanges();
 * obj->addNum(value);
 * vector<vector<int>> param_2 = obj->getIntervals();
 */