## Approach 1: Brute Force

• Time:Constructor: O(1), book(start: int, end: int): O(n^2)
• Space:O(n)

## C++

``````class MyCalendarTwo {
public:
bool book(int start, int end) {
for (const auto& [s, e] : overlaps)
if (max(start, s) < min(end, e))
return false;

for (const auto& [s, e] : ranges) {
const int ss = max(start, s);
const int ee = min(end, e);
if (ss < ee)
overlaps.emplace_back(ss, ee);
}

ranges.emplace_back(start, end);
return true;
}

private:
vector<pair<int, int>> ranges;
vector<pair<int, int>> overlaps;
};
``````

## JAVA

``````class MyCalendarTwo {
public boolean book(int start, int end) {
for (int[] overlap : overlaps)
if (Math.max(start, overlap[0]) < Math.min(end, overlap[1]))
return false;

for (int[] range : ranges) {
final int maxStart = Math.max(start, range[0]);
final int minEnd = Math.min(end, range[1]);
if (maxStart < minEnd)
}

return true;
}

List<int[]> ranges = new ArrayList<>();
List<int[]> overlaps = new ArrayList<>();
}
``````

## Approach 2: Ordered Map

• Time:Constructor: O(1), book(start: int, end: int): O(n\log n)
• Space:O(n)

## C++

``````class MyCalendarTwo {
public:
bool book(int start, int end) {
++timeline[start];
--timeline[end];

int activeEvents = 0;

for (const auto& [_, count] : timeline) {
activeEvents += count;
if (activeEvents > 2) {
if (--timeline[start] == 0)
timeline.erase(start);
if (++timeline[end] == 0)
timeline.erase(end);
return false;
}
}

return true;
}

private:
map<int, int> timeline;
};
``````

## JAVA

``````class MyCalendarTwo {
public boolean book(int start, int end) {
timeline.merge(start, 1, Integer::sum);
timeline.merge(end, -1, Integer::sum);

int activeEvents = 0;

for (final int count : timeline.values()) {
activeEvents += count;
if (activeEvents > 2) {
timeline.merge(start, -1, Integer::sum);
if (timeline.get(start) == 0)
timeline.remove(start);
timeline.merge(end, 1, Integer::sum);
if (timeline.get(end) == 0)
timeline.remove(end);
return false;
}
}

return true;
}

private Map<Integer, Integer> timeline = new TreeMap<>();
}
``````