Sponsored
Sponsored
In this approach, we maintain two separate lists: `single_booked` for bookings that have been added without conflicts, and `double_booked` for intervals where two events overlap. To add a new booking:
Time Complexity: O(N^2) because for each booking, we might need to check with all existing ones.
Space Complexity: O(N) to store all bookings.
1class MyCalendarTwo:
2 def __init__(self):
3 self.single_booked = []
4 self.double_booked = []
5
6This Python solution uses two lists to manage single and double bookings respectively. A potential triple booking is checked before any modification of `double_booked`. New booking is always appended to `single_booked` after checks.
In this approach, we use a segment tree to efficiently keep track of overlapping intervals. By maintaining a segment tree, we can:
This approach is optimal for datasets with large integer boundaries due to the logarithmic nature of segment trees for both update and query operations.
Time Complexity: O(N log N) due to map operations.
Space Complexity: O(N) for map storage.
1
class MyCalendarTwo {
public:
std::map<int, int> timeline;
MyCalendarTwo() {}
bool book(int start, int end) {
timeline[start]++;
timeline[end]--;
int ongoing = 0;
for (const auto &entry : timeline) {
ongoing += entry.second;
if (ongoing >= 3) {
timeline[start]--;
timeline[end]++;
return false;
}
}
return true;
}
};The C++ solution uses a `map` to simulate a segment tree on a line sweep basis. As intervals are booked or end, we increment or decrement from the timeline, respectively. The `book` method tracks active bookings to ensure it never surpasses two overlapping intervals.