Ugly but very easy-to-understand c++ solution, O(logn) time per adding


  • 0

    The key is to find the correct position to insert a new interval or merge two adjacent intervals, so binary search is trivial. Be careful with corners.
    Codes below are self-explained.

    class SummaryRanges {
    private:
        vector<Interval> intervals;
    
    public:
        SummaryRanges() { }
        
        void addNum(int val) {
            if (intervals.empty()) {
                intervals.push_back(Interval(val, val));
                return;
            }
            auto i = upper_bound(intervals.begin(), intervals.end(), val, [](const int lhs, const Interval rhs) { return lhs < rhs.start; });
            if (i == intervals.end()) {
                auto last = intervals.end() - 1;
                if (val <= last->end) return;
                if (val == last->end + 1) last->end += 1;
                else intervals.push_back(Interval(val, val));
            } else if (i == intervals.begin()) {
                auto first = intervals.begin();
                if (val == first->start - 1) first->start -= 1;
                else intervals.insert(first, Interval(val, val));
            } else {
                auto prev = i - 1;
                if (val <= prev->end) return;
                if (val == prev->end + 1) {
                    if (val == i->start - 1) { // merge
                        i->start = prev->start;
                        intervals.erase(prev);
                    } else {
                        prev->end += 1;
                    }
                } else {
                    if (val == i->start - 1) i->start -= 1;
                    else intervals.insert(i, Interval(val, val));
                }
            }
        }
        
        vector<Interval> getIntervals() {
            return intervals;    
        }
    };

Log in to reply
 

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