#### Approach #1: Brute Force [Accepted]

Intuition

Maintain a list of bookings and a list of double bookings. When booking a new event [start, end), if it conflicts with a double booking, it will have a triple booking and be invalid. Otherwise, parts that overlap the calendar will be a double booking.

Algorithm

Evidently, two events [s1, e1) and [s2, e2) do not conflict if and only if one of them starts after the other one ends: either e1 <= s2 OR e2 <= s1. By De Morgan's laws, this means the events conflict when s1 < e2 AND s2 < e1.

If our event conflicts with a double booking, it's invalid. Otherwise, we add conflicts with the calendar to our double bookings, and add the event to our calendar.

Complexity Analysis

• Time Complexity: , where is the number of events booked. For each new event, we process every previous event to decide whether the new event can be booked. This leads to complexity.

• Space Complexity: , the size of the calendar.

#### Approach #2: Boundary Count [Accepted]

Intuition and Algorithm

When booking a new event [start, end), count delta[start]++ and delta[end]--. When processing the values of delta in sorted order of their keys, the running sum active is the number of events open at that time. If the sum is 3 or more, that time is (at least) triple booked.

A Python implementation was not included for this approach because there is no analog to TreeMap available.

class MyCalendarTwo {
TreeMap<Integer, Integer> delta;

public MyCalendarTwo() {
delta = new TreeMap();
}

public boolean book(int start, int end) {
delta.put(start, delta.getOrDefault(start, 0) + 1);
delta.put(end, delta.getOrDefault(end, 0) - 1);

int active = 0;
for (int d: delta.values()) {
active += d;
if (active >= 3) {
delta.put(start, delta.get(start) - 1);
delta.put(end, delta.get(end) + 1);
if (delta.get(start) == 0)
delta.remove(start);
return false;
}
}
return true;
}
}


Complexity Analysis

• Time Complexity: , where is the number of events booked. For each new event, we traverse delta in time.

• Space Complexity: , the size of delta.

Analysis written by: @awice. Solution in Approach #2 inspired by @cchao.