O(log n) method with binary search and index mapping in C++


  • -1
    H
    /**
     * Definition for an interval.
     * struct Interval {
     *     int start;
     *     int end;
     *     Interval() : start(0), end(0) {}
     *     Interval(int s, int e) : start(s), end(e) {}
     * };
     */
    class Solution {
    public:
        int findPos(vector<Interval>& intervals, int t) {
            // return x such that A(x) <= t < A(x+1)
            if (t < intervals.begin()->start) return -1;
            if (t > intervals.rbegin()->end) return intervals.size() * 2 - 1;
            int l = 0, r = intervals.size() * 2 - 1;
            #define A(i) ((i%2)?(intervals[i/2].end):(intervals[i/2].start))
            while (l <= r) {
                int m = l + (r-l)/2;
                int v = A(m);
                if (v > t) {
                    r = m-1;
                } else if (v < t) {
                    l = m+1;
                } else return m;
            }
            return r;
        }
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            if (intervals.empty()) {
                intervals.push_back(newInterval);
                return intervals;
            }
            // (0, 1) (2, 3) (4 5) ...
            // -1 0  1   2  3  4  5 ...
            int spos = findPos(intervals, newInterval.start);
            int epos = findPos(intervals, newInterval.end);
            int rems, reme;
            
            if (spos%2 && spos >= 0 && A(spos) == newInterval.start) {
                spos--;
                newInterval.start = A(spos);
            }
            if (epos%2==0 && epos < intervals.size()*2 && A(epos) == newInterval.end) {
                epos++;
                newInterval.end = A(epos);
            }
            
            //cout<<newInterval.start<<"--"<<newInterval.end<<endl;
            //cout<<spos<<"--"<<epos<<endl;
            
            if (spos % 2) {
                if (epos % 2) {
                    rems = (spos+1)/2;
                    reme = (epos-1)/2;
                } else {
                    rems = (spos+1)/2;
                    reme = (epos)/2;
                    newInterval.end = (intervals.begin()+reme)->end;
                }
            } else {
                if (epos % 2) {
                    rems = (spos)/2;
                    reme = (epos-1)/2;
                    newInterval.start = (intervals.begin()+rems)->start;
                } else {
                    rems = (spos)/2;
                    reme = (epos)/2;
                    newInterval.start = (intervals.begin()+rems)->start;
                    newInterval.end = (intervals.begin()+reme)->end;
                }
            }
            //cout<<rems<<"--"<<reme<<endl;
            intervals.erase(intervals.begin()+rems, intervals.begin()+reme+1);
            intervals.insert(intervals.begin()+rems, newInterval);
            return intervals;
        }
    };

Log in to reply
 

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