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.
1using System.Collections.Generic;
2
3public class MyCalendarTwo {
4 private List<int[]> single_booked;
5 private List<int[]> double_booked;
6
7 public MyCalendarTwo() {
8 single_booked = new List<int[]>();
9 double_booked = new List<int[]>();
10 }
11
12 public bool Book(int start, int end) {
13 foreach (var interval in double_booked) {
14 if (interval[0] < end && start < interval[1]) {
return false;
}
}
foreach (var interval in single_booked) {
if (interval[0] < end && start < interval[1]) {
double_booked.Add(new int[] {Math.Max(start, interval[0]), Math.Min(end, interval[1])});
}
}
single_booked.Add(new int[] {start, end});
return true;
}
}The C# solution involves using List collections to track overlapping booking intervals. The `Book` method ensures no triple bookings occur by validating overlap within `double_booked` before adding the new interval 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
The Python solution employs `SortedDict` from `sortedcontainers` to manage bookings efficiently. With each booking event, the timeline is checked for overlap counts that could imply triple booking, altering the dictionary accordingly.