C++ Solution using a set<Interval>


  • 0
    G
    struct Comp
    {
        bool operator()(const Interval& I1, const Interval& I2)
        {
            return I1.start < I2.start ||(I1.start == I2.start && I1.end < I2.end);
        }
    };
    
    class SummaryRanges {
    public:
        /** Initialize your data structure here. */
        
        set<Interval,Comp> Tree;
        
        SummaryRanges() {
            
        }
        
        void addNum(int val) 
        {
            Interval I(val,val);
            
            if(Tree.empty())
            {
                Tree.insert(I);
                return;
            }
        
            auto LB = Tree.lower_bound(I);
            
            if(LB != Tree.begin())
            {
                if(prev(LB)->end >= val - 1)
                {
                    I.start = prev(LB)->start;
                    I.end = max(I.end,prev(LB)->end);
                    Tree.erase(prev(LB));
                }
            }
            
            if(LB != Tree.end())
            {
                if(LB->start <= val + 1)
                {
                    I.start = min(LB->start,I.start);
                    I.end = LB->end;
                    Tree.erase(LB);
                }
            }
            
            Tree.insert(I);
        }
        
        vector<Interval> getIntervals() 
        {
            return (vector<Interval>(Tree.begin(),Tree.end()));    
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.