65ms beats 95.69%, O(lgn+2n+2) map+binary search


  • 1
    E

    In my calendar 1, an interval(start+end) is a pair<int,int>(start,end), I can sort pairs because there is no overlap which means the pre-pair.end<=next-pair.start. So binary search a whole pair can work.
    In this problem, pairs can have overlap with each other, so we don't need to make "start+end" a pair, because sort or binary search can't work.
    But I can split them, and take an interval as two independent points "start" and "end", then sort them and binary search them.

    class MyCalendarTwo{
    private:
        map<int,int>intervals;
    /**structure of intervals:
    each pair in intervals:(k,v)
    k is a point (start or end of an interval)
    v is the number of overlaps between the point of k and the next point of k.
    so v can be 0, 1, 2
    **/
    /**rules of "can insert" and "can't insert" for a new interval(s,e)
    The graph below:
      a point p in intervals which is not large than s or e
      o------o means a segment
      if s or e is above or below of p, means p==s or p==e
      if s or e is right of p, means p<s or p<e
      use "k:v" to represent each point
      x means s or e can't insert
      =>? means if p is in the interval of (s,e), the v of p will change into ?
    
    1:
                    s:1    s:1
    o----------------o  
                    p:0 => p:1
                    e:0    e:0
    2:
                    s:1    s:1
    o----------------o
    o----------------o  
                    p:0 => p:x
                    e:x    e:x
    3:
                    s:2    s:2
                     o----------------o
                    p:1 => p:2
                    e:1    e:1
    4:
                    s:2    s:2
            o---------------------o
       o-------------o
                    p:1 => p:x
                    e:x    e:x
    5:
                    s:x    s:x
                     o----------------o
                     o----------------o
                    p:2 => p:x
                    e:2    e:x
    6:
                    s:x    s:x
              o----------------------o
                     o----------------o
                    p:2 => p:x
                    e:2    e:x
    
    don't need to consider 2 and 4, so we only need to consider 1,3,5,6,and 5 is the same as 6, so there are only 3 states.
    **/
    public:
        MyCalendarTwo() {}
        bool book(int start, int end){
            if(intervals.empty()){insert(start,end);return true;}
            auto it=intervals.lower_bound(start);
            if(it==intervals.end()){insert(start,end);return true;}
            int t1=0;//start:t1
            if(it->first!=start&&it!=intervals.begin()&&(t1=prev(it,1)->second)==2)return false; //check if start can be inserted
            int t2=t1;//start:t2
            auto it2=it;
            for(;it2!=intervals.end()&&it2->first<end;it2++){//check the points between start and end
                if(it2->second==2)return false;
            }
            for(it2=it;it2!=intervals.end()&&it2->first<end;it2++){//change the value of pionts
                t2=it2->second;it2->second++;
            }
            if(it2->first!=end)intervals.emplace_hint(it2,end,t2);//insert end
            if(it->first!=start)intervals.emplace_hint(it,start,t1+1);//insert start
            return true;
        }
        void insert(int start,int end){
            intervals.emplace_hint(intervals.end(),start,1);
            intervals.emplace_hint(intervals.end(),end,0);
        }
    };
    

    complex of program:
    binary search start: lgn
    check each point: n
    change the value of each point:n
    insert start and end(because I have found the position of insert): <<lgn and close to O(1)
    On=O(lgn+2n+2)


Log in to reply
 

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