352. Data Stream as Disjoint Intervals - cocoder39/coco39_LC GitHub Wiki

352. Data Stream as Disjoint Intervals

use set such that the complexity of insertion is O(log n) where n is the size of the data stream. the most essential method is addNum(). st.lower_bound(Interval(val, val)) return an iterator it where it == st.end() || it->start >= val. Therefore, *it may not be the first Interval that would be affected by val. Thus, we check if it worth moving one step back through if(it != st.begin() && (--it)->end + 1 < val). val can extend an existing Interval only if val is one distance away from the Interval.

tips: comparator of std::set

sort Interval in std::set through. std::set sends const-references to the comparator, which won't work if the comparator requires non-const references. You can send mutable references to a function requesting immutable references; the reverse is not the case.

struct Cmp{
        bool operator()(const Interval& a, const Interval& b) { return a.start < b.start;}
//      bool operator()(Interval& a, Interval& b) { return a.start < b.start;} //error
//      bool operator()(Interval a, Interval b) { return a.start < b.start;} //works
    };
    set<Interval, Cmp> st;

class SummaryRanges {
public:
    /** Initialize your data structure here. */
    SummaryRanges() {
        
    }
    
    void addNum(int val) { //O(n * log n)
        auto it = st.lower_bound(Interval(val, val)); //it->start >= val
        int start = val, end = val;
        if(it != st.begin() && (--it)->end + 1 < val) { 
            //if it->start < val && it->end + 1 < val, it++;
            //if it->start < val && it->end + 1 >= val, it = it;
            it++;
        }
        while(it != st.end() && it->start - 1 <= val && it->end + 1 >= val)
        {
            start = min(start, it->start);
            end = max(end, it->end);
            it = st.erase(it);
        }
        st.insert(it,Interval(start, end));
    }
    
    vector<Interval> getIntervals() {
        vector<Interval> res;
        for (auto &i : st) {
            res.push_back(i);
        }
        return res;
    }
private:
    struct Cmp{
        bool operator()(const Interval& a, const Interval& b) { return a.start < b.start;}
//      bool operator()(Interval& a, Interval& b) { return a.start < b.start;} //error
//      bool operator()(Interval a, Interval b) { return a.start < b.start;} //works
    };
    set<Interval, Cmp> st;
};
⚠️ **GitHub.com Fallback** ⚠️