Data Stream as Disjoint Intervals -- LeetCode

[Question]

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]

[Analysis]
Given a new number A, using Binary Search Tree can find the relevant intervals in O(LogN) time complexity, where N is the number of collected intervals. The relevant intervals are the 'previous' and 'next' intervals, closest intervals to A and their 'end' values are smaller or larger(or equal to) than A, respectfully. In C++, the data structure BST can use 'std::set', 'std::map' in STL.

The 'std::map' may provide an easier implementation. Define map<int,int>, map[end]=start for interval [start,end]. Use lower_bound() to quickly (O(LogN)) check the position where a new number will end up with.

[Solution]
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class SummaryRanges {
    map<int, int> buf;
   
public:
    /** Initialize your data structure here. */
    SummaryRanges() {
    }
   
    void addNum(int val) {
        if (buf.empty()) {
            buf[val]=val;
            return;
        }
       
        auto it=buf.lower_bound( val );
        if (it==buf.end())
            buf[val]=(buf.count(val-1))?buf[val-1]:val;
        else {
            if (it->second <= val) return;
            if (it->second  == val+1)
                it->second = (buf.count(val-1))?buf[val-1]:val;
            else
                buf[val]=(buf.count(val-1))?buf[val-1]:val;
        }
        buf.erase(val-1);
    }
   
    vector<Interval> getIntervals() {
        vector<Interval> res;
       
        for (auto& pr: buf)
            res.push_back( Interval(pr.second, pr.first) );
        return res;
    }
};

//
// Another solution if getIntervals() is less frequently called.
//
class SummaryRanges {
    set<int> buf;
 
public:
    /** Initialize your data structure here. */
    SummaryRanges() {
    }
 
    void addNum(int val) {
        buf.insert(val);
    }
 
    vector<Interval> getIntervals() {
        vector<Interval> res;
        int start=-1, end=-1;
        for (auto& n: buf) {
            if (res.empty()|| n!=res.back().end+1)
                res.push_back(Interval(n, n));
            if (n == res.back().end+1)
                res.back().end=n;
        }
        return res;
    }
};