Interval maps -- cheap alternative to segment tree

interval-map.md

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

The basic idea is to use map : start -> end where end is not inclusive. Invariant is that this map is always disjoint.

lc

class SummaryRanges {
    map<int, int> m; // start to end, [x,y)
public:
    /** Initialize your data structure here. */
    SummaryRanges() {
    }
    
    void addNum(int val) {
        auto next = m.upper_bound(val); // x .. [,)
        if (next != begin(m)) {
            auto cur = prev(next);
            int end = cur->second;
            // adds to end of existing interval
            if (val  == cur->second) {
                int start = cur->first;
                end = val+1;
                // merge two existing intervals
                if (val + 1 == next->first) {
                    end = next->second;
                    ++next;
                    m.erase(cur, next);
                } else {
                    m.erase(cur);
                }
                m.emplace(start, end);
            } else if (val > cur->second) { // [) .. x
                if (val+1 == next->first) {
                    int end = next->second;
                    m.erase(next);
                    m.emplace(val, end);
                } else {
                    m.emplace(val, val + 1);
                }
            } else {
                // [ x ) --> nothing
            }
        } else {
            int end = val + 1;
             // the only situation when it merges is x [x+1, y)
            if (end == next->first) {
                end = next->second;
                m.erase(next);
            }
            m.emplace(val, end);
        }
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> res;
        res.reserve(m.size());
        for (auto[start, end] : m) {
            res.emplace_back( vector<int>{start, end-1} );
        }
        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();
 */