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

• 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)

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