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.
1import java.util.ArrayList;
2import java.util.List;
3
4class MyCalendarTwo {
5 private List<int
In the Java solution, two ArrayLists keep track of booked intervals. The `book` method first checks for potential triple bookings, avoids adding to `double_booked` if safe, ultimately appending the new booking 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.
1using System.Collections.Generic;
public class MyCalendarTwo {
private SortedDictionary<int, int> timeline;
public MyCalendarTwo() {
timeline = new SortedDictionary<int, int>();
}
public bool Book(int start, int end) {
if (!timeline.ContainsKey(start)) timeline[start] = 0;
if (!timeline.ContainsKey(end)) timeline[end] = 0;
timeline[start]++;
timeline[end]--;
int ongoing = 0;
foreach (var kvp in timeline) {
ongoing += kvp.Value;
if (ongoing >= 3) {
timeline[start]--;
timeline[end]++;
return false;
}
}
return true;
}
}
The C# approach uses a `SortedDictionary` to handle the booking timeline. This structure facilitates booking quickly by checking and updating intervals, ensuring no triple bookings occur.