352. Data Stream as Disjoint Intervals

https://leetcode.com/problems/data-stream-as-disjoint-intervals/

Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

Follow up:

What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?

给定一个非负整数流，对截止到当前的不相交区间进行汇总。每次插入一个新数val对区间做合并，维持区间用tree map存。合并时分类讨论，拿到比val小的数作为区间start的指针l，和比val大的数作为区间start的指针r，合并只可能和l和r相关。

class SummaryRanges {
public:
    map<int, int> m;
    /** Initialize your data structure here. */
    SummaryRanges() {
        
    }
    
    void addNum(int val) {
        if (m.count(val)) return;
        const auto r = m.upper_bound(val), l = (r == m.begin()) ? m.end() : prev(r);
        if (l != m.end() && r != m.end() && l->second + 1 == val && val + 1 == r->first) {
            l->second = r->second;
            m.erase(r);
        } else if (l != m.end() && l->second + 1 >= val) {
            l->second = max(l->second, val);
        } else if (r != m.end() && val + 1 == r->first) {
            m[val] = r->second;
            m.erase(r);
        } else {
            m[val] = val;
        }
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> res;
        for (const auto &p : m) {
            res.push_back({p.first, p.second});
        }
        return res;
    }
};

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