C++ 99ms beats 99.8% using set


  • 0
    F
    #include <set>
    
    struct comp {
        bool operator()(const Interval &iv1, const Interval &iv2) const {
            return iv1.start<iv2.start;
        }
    };
    
    class SummaryRanges {
    public:
        void addNum(int val) {
            Interval iv(val, val);
            if( ! intervals.empty() ) {
               // find the intervals after val
               auto Iu = intervals.upper_bound(iv);
               // handle before
               if( Iu != intervals.begin() ) {
                   auto Il = std::prev(Iu);
                   if(Il->end >= val) return;
                   if(Il->end==val-1) {
                       iv.start = Il->start;
                       intervals.erase(Il);
                   }
               }
               // handle after
               if( Iu != intervals.end() )
                   if(Iu->start == val+1) {
                       iv.end = Iu->end;
                       intervals.erase(Iu);
                   }
            }
            intervals.insert(iv);
        }
    
        std::vector<Interval> getIntervals() {
            return std::vector<Interval>(intervals.begin(), intervals.end());
        }
    private:
        std::set<Interval, comp> intervals;
    };
    

Log in to reply
 

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