# C++ O(N) solution

• The max number of overlap is the same and the max number of times a start time is covered.
So we put all intervals in a list, and also a map to count the number of times each start time is covered.
Update the map each time we put in a new interval.

``````class MyCalendarTwo {
public:
vector<pair<int,int>> st;
map<int,int> mp;
MyCalendarTwo() {
}

bool book(int s, int e) {
for (auto it = mp.lower_bound(s); it != mp.end() && it->first < e; ++it) {
if (it->second >= 2) return false;
}
int cnt = 0;
for (auto &v:st) if (v.first <=s && v.second > s) ++cnt;
if (cnt >=2) return false;
for (auto it = mp.lower_bound(s); it != mp.end() && it->first < e; ++it)
++it->second;
mp[s] = cnt + 1;
st.push_back({s,e});
return true;
}
};
``````

• This solution is not O(N). insertion into a map is a log N operation.

• @andreirtaylor O(N) each call. In any case, the map insertion isn't the bottleneck

• This post is deleted!

• @huangjipengnju how so? Where is the O(nlogn) part?

• This post is deleted!

• @huangjipengnju Traversing the tree, red-black or not is O(n). Looking for the start iterator is O(logn) but it is only done once. So the complexity is still O(n).

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