Binary Search with 112ms


  • 0
    D

    Find the largest interval that is on the left of the given value (with binary search).
    After that, three cases should be discussed:

    1. value is on the most left position
    2. value is on the most right position
    3. value is between two intervals
      Tips: if value has already appeared, just return
    class SummaryRanges {
    public:
        /** Initialize your data structure here. */
        vector<Interval> res;
        
        int find(int val) {
            int l = 0, r = res.size() - 1;
            while(l <= r) {
                int m = (l + r) / 2;
                if(res[m].end >= val && res[m].start <= val)
                    return -2;
                if(res[m].end < val)
                    l = m + 1;
                else
                    r = m - 1;
            }
            return r;
        }
        
        SummaryRanges() {
            
        }
        
        void addNum(int val) {
            Interval add(val, val);
            if(res.size() == 0) {
                res.push_back(add);
                return;
            }
            
            int len = res.size();
            int index = find(val);
            if(index == -2)
                return;
    
            if(index == -1) {
                if(res[0].start > val + 1)
                    res.insert(res.begin(), add);
                else
                    res[0].start = val;
            }
            else if(index == len - 1) {
                if(res[index].end < val - 1)
                    res.push_back(add);
                else
                    res[index].end = val;
            }
            else {
                if(res[index].end == val - 1) {
                    res[index].end = val;
                    if(res[index+1].start == val + 1) {
                        res[index].end = res[index+1].end;
                        res.erase(res.begin() + index + 1);
                    }
                }
                else {
                    if(res[index+1].start == val + 1)
                        res[index+1].start = val;
                    else
                        res.insert(res.begin() + index + 1, add);
                }
            }
        }
        
        vector<Interval> getIntervals() {
            return res;
        }
    };
    

Log in to reply
 

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