You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.
A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).
The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.
Implement the MyCalendarTwo class:
MyCalendarTwo() Initializes the calendar object.boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.Example 1:
Input ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] Output [null, true, true, true, false, true, true] Explanation MyCalendarTwo myCalendarTwo = new MyCalendarTwo(); myCalendarTwo.book(10, 20); // return True, The event can be booked. myCalendarTwo.book(50, 60); // return True, The event can be booked. myCalendarTwo.book(10, 40); // return True, The event can be double booked. myCalendarTwo.book(5, 15); // return False, The event cannot be booked, because it would result in a triple booking. myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked. myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.
Constraints:
0 <= start < end <= 1091000 calls will be made to book.In #731 My Calendar II, you must design a calendar that allows booking time intervals as long as no time is booked more than twice. The main challenge is detecting when a new interval would create a triple overlap.
A common strategy is to maintain two collections: one for all booked intervals and another for intervals that are already double-booked. When a new event is requested, first check if it overlaps with any interval in the double-booked list. If it does, the booking would cause a triple overlap and must be rejected. Otherwise, compute overlaps between the new event and existing bookings and store those overlaps as double-booked intervals.
Another approach uses a sweep line / prefix sum technique with an ordered map that tracks +1 at the start time and -1 at the end time. By scanning the running count, you ensure the active bookings never exceed two.
These approaches rely on interval handling, ordered data structures, and careful overlap detection. Typical operations run in O(n) time per booking with O(n) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Overlap Tracking with Double-Booked Intervals | O(n) per booking | O(n) |
| Sweep Line with Ordered Map / Prefix Sum | O(n log n) per booking | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Store two sorted lists of intervals: one list will be all times that are at least single booked, and another list will be all times that are definitely double booked. If none of the double bookings conflict, then the booking will succeed, and you should update your single and double bookings accordingly.
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) {
foreach (var interval in double_booked) {
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
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;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of interval booking and calendar design problems appear in FAANG-style interviews. They test understanding of interval overlaps, sweep line algorithms, and efficient data structure design.
Common solutions use interval lists along with overlap tracking, or an ordered map for a sweep line approach. Ordered maps or TreeMaps are useful for maintaining prefix counts of active bookings while scanning time points.
A widely used approach keeps two lists: one for all bookings and another for double-booked intervals. Before inserting a new interval, check if it overlaps with any double-booked interval. If it does, the booking would create a triple overlap and must be rejected.
Tracking double-booked intervals helps quickly detect whether a new event would create a triple overlap. If the new interval intersects with any existing double-booked range, it means three events would overlap at that time.
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.