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.
1#include <vector>
2#include <algorithm>
3
4class MyCalendarTwo {
5public:
6 std::vector<std::pair<int, int>> single_booked;
7 std::vector<std::pair<int, int>> double_booked;
8
9 MyCalendarTwo() {}
10
11 bool book(int start, int end) {
12 for (const auto& interval : double_booked) {
13 if (interval.first < end && start < interval.second) {
14 return false;
}
}
for (const auto& interval : single_booked) {
if (interval.first < end && start < interval.second) {
double_booked.push_back({std::max(start, interval.first), std::min(end, interval.second)});
}
}
single_booked.push_back({start, end});
return true;
}
};The C++ implementation uses the vector of pairs to maintain intervals. It compares overlaps and adds to `double_booked` if necessary before any new booking gets appended to `single_booked`.
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
In this Java implementation, a `TreeMap` handles the timeline intervals and their overlap. Modification occurs directly within the map, allowing event queries to ensure the absence of triple bookings.