How to Solve My Calendar II

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

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.

How GhostInterview Helps

• Automatically generates the correct event insertion logic, highlighting where overlaps cause triple bookings.
• Guides you through managing two interval lists and applying binary search to prevent inefficient scans.
• Identifies edge cases such as adjacent intervals and boundary overlaps, ensuring correct booking results.

Topic Pages

• Array
• Binary Search
• Design
• Segment Tree
• Prefix Sum
• Ordered Set

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.