# Three different ways

• `O(n^2)`

``````class MyCalendar {
vector<pair<int, int>> intervals;
public:
MyCalendar() {

}

bool overlap(pair<int, int> p, int s, int e) {
return s < p.second && e > p.first;
}

bool book(int start, int end) {
for (auto& p : intervals) if (overlap(p, start, end)) return false;
intervals.push_back({start, end});
return true;
}
};
``````

`O(nlogn)`
Find the first end bigger than the current start:

``````class MyCalendar {
map<int, int> m;
public:
MyCalendar() {

}

bool book(int start, int end) {
auto it = m.upper_bound(start);
if (it == m.end()) {
m.insert(it == m.begin() ? it : --it, {end, start}); // m.insert({end, start}) also works. Use iterator as a hint can make insertion faster?
return true;
} else {
if (end > it->second) return false;
else {
m.insert(it == m.begin() ? it : --it, {end, start});
return true;
}
}
}
};
``````

`O(nlogn)`

Find the first start bigger than the current end:

``````class MyCalendar {
map<int, int> m;
public:
MyCalendar() {

}

bool book(int start, int end) {
auto it = m.lower_bound(end);
if (it != m.begin()) --it;
else {
m.insert(it, {start, end}); // m.insert({start, end}) also works. Use iterator as a hint can make insertion faster?
return true;
}
if (it->second > start) return false;
else {
m.insert(it, {start, end});
return true;
}
}
};
``````

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