LeetCode Problem Workspace
My Calendar II
Implement a calendar that allows double bookings but prevents triple bookings, managing overlapping intervals efficiently with binary search.
6
Topics
6
Code langs
3
Related
Practice Focus
Medium · Binary search over the valid answer space
Answer-first summary
Implement a calendar that allows double bookings but prevents triple bookings, managing overlapping intervals efficiently with binary search.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for Binary search over the valid answer space
This problem requires designing a calendar system that can track events while preventing any triple booking. The key is to maintain overlapping intervals and verify that adding a new event does not create a conflict with existing double bookings. A binary search approach over the interval lists ensures efficient insertion and conflict detection, making the solution scalable for multiple bookings.
Problem Statement
You are tasked with creating a calendar program where events can be booked on half-open intervals [startTime, endTime). An event can be successfully added if it does not create a triple booking with existing events, meaning no moment is shared by three events simultaneously.
Implement a class MyCalendarTwo with a method book(startTime, endTime) that returns true if the event can be added without causing a triple booking and false otherwise. Events are represented by integer intervals, and you must handle up to 1000 bookings efficiently, ensuring overlapping intervals are properly managed.
Examples
Example 1
Input: See original problem statement.
Output: See original problem statement.
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 <= 109
- At most 1000 calls will be made to book.
Solution Approach
Maintain two lists for interval tracking
Store two sorted lists: one for all single-booked intervals and another for intervals that are already double-booked. When adding a new event, check for overlaps with the double-booked list first to avoid triple bookings.
Binary search for efficient insertion
Use binary search to quickly locate where the new event would overlap with existing intervals in both lists. This minimizes scanning and keeps insertion operations efficient, adhering to the pattern of binary search over the valid answer space.
Update overlapping intervals
After confirming no triple booking occurs, update the double-booked list with any new overlaps created by the event and insert the event into the single-booked list. This ensures subsequent bookings correctly respect existing overlaps.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(N) |
| Space | O(N) |
Time complexity is O(N) per booking in the worst case due to overlap checks, and space complexity is O(N) to store single- and double-booked intervals.
What Interviewers Usually Probe
- Look for efficient interval insertion and overlap detection.
- Check if the candidate correctly handles double bookings without creating triples.
- Listen for binary search usage when scanning for potential conflicts.
Common Pitfalls or Variants
Common pitfalls
- Failing to check double-booked intervals first, leading to inadvertent triple bookings.
- Inserting events without maintaining sorted interval lists, which slows down future checks.
- Overlapping calculations off by one, misunderstanding the half-open interval definition.
Follow-up variants
- Modify to allow at most K bookings per time slot instead of two.
- Use a segment tree to handle a larger range of time values more efficiently.
- Implement the same calendar logic but for continuous real-number time ranges instead of integer times.
FAQ
What is the key pattern used in My Calendar II?
The problem uses binary search over the valid answer space to efficiently check and insert intervals while avoiding triple bookings.
Can a single time slot be booked more than twice?
No, the calendar allows at most double bookings, and any attempt to create a triple booking returns false.
Why maintain two separate interval lists?
One list tracks all single-booked intervals and another tracks double-booked intervals, ensuring triple bookings can be detected quickly.
What is the time complexity of booking an event?
Each booking operation is O(N) in the worst case because it may need to check overlaps against existing intervals, though binary search helps reduce scanning time.
How do half-open intervals affect booking logic?
Intervals are [startTime, endTime), so the end time is exclusive, preventing accidental overlap counting at boundaries.
Solution
Solution 1: Difference Array
We can use the concept of a difference array to record the booking status at each time point. Then, we traverse all the time points and count the booking status at the current time point. If the number of bookings exceeds $2$, we return $\textit{false}$. Otherwise, we return $\textit{true}$.
class MyCalendarTwo:
def __init__(self):
self.sd = SortedDict()
def book(self, startTime: int, endTime: int) -> bool:
self.sd[startTime] = self.sd.get(startTime, 0) + 1
self.sd[endTime] = self.sd.get(endTime, 0) - 1
s = 0
for v in self.sd.values():
s += v
if s > 2:
self.sd[startTime] -= 1
self.sd[endTime] += 1
return False
return True
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(startTime,endTime)Solution 2: Segment Tree
A segment tree divides the entire interval into multiple non-contiguous subintervals, with the number of subintervals not exceeding $\log(\textit{width})$. To update the value of an element, only $\log(\textit{width})$ intervals need to be updated, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, a **lazy mark** is used to ensure efficiency.
class MyCalendarTwo:
def __init__(self):
self.sd = SortedDict()
def book(self, startTime: int, endTime: int) -> bool:
self.sd[startTime] = self.sd.get(startTime, 0) + 1
self.sd[endTime] = self.sd.get(endTime, 0) - 1
s = 0
for v in self.sd.values():
s += v
if s > 2:
self.sd[startTime] -= 1
self.sd[endTime] += 1
return False
return True
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(startTime,endTime)Continue Topic
array
Practice more edge cases under the same topic.
arrow_forwardauto_awesomeContinue Pattern
Binary search over the valid answer space
Expand the same solving frame across more problems.
arrow_forwardsignal_cellular_altSame Difficulty Track
Medium
Stay on this level to stabilize interview delivery.
arrow_forward