Problem Description

You need to implement a calendar system that can handle event bookings while preventing triple bookings. A triple booking occurs when three events overlap at any point in time.

Each event is represented by a [startTime, endTime) interval, which means the event includes the startTime but excludes the endTime (half-open interval). For example, [10, 20) means the event runs from time 10 (inclusive) to time 20 (exclusive).

You need to implement a MyCalendarTwo class with two methods:

1. MyCalendarTwo(): Initializes an empty calendar object
2. book(startTime, endTime): Attempts to add a new event to the calendar
   • Returns true if the event can be added without causing a triple booking (no point in time has 3 or more overlapping events)
   • Returns false if adding this event would cause a triple booking, and the event should not be added

The solution uses a difference array approach with a SortedDict to track the number of concurrent events at each time point. When booking an event:

• It increments the count at startTime by 1 (event starts)
• It decrements the count at endTime by 1 (event ends)
• It then iterates through all time points in order, maintaining a running sum of active events
• If at any point the running sum exceeds 2 (meaning 3+ events overlap), it reverts the changes and returns false
• Otherwise, the booking is successful and returns true

This approach efficiently handles the constraint that at most 2 events can overlap at any given time.

Intuition

The key insight is to think about how overlapping events affect the number of concurrent bookings at any point in time. Instead of storing complete intervals and checking overlaps between every pair of events, we can track the "change points" where events start and end.

Imagine a timeline where events are happening. When an event starts at time t, the number of concurrent events increases by 1. When an event ends at time t, the number of concurrent events decreases by 1. This is the core idea behind the difference array approach.

For example, if we have events [10, 20) and [15, 25):

• At time 10: +1 event (total: 1)
• At time 15: +1 event (total: 2)
• At time 20: -1 event (total: 1)
• At time 25: -1 event (total: 0)

By maintaining these change points in sorted order, we can efficiently calculate the number of concurrent events at any moment by summing up all the changes from the beginning up to that point. This running sum tells us exactly how many events are active.

The beauty of this approach is that we don't need to explicitly check every possible overlap combination. We just need to ensure that when we add a new event, the running sum never exceeds 2 at any point. If it would exceed 2, we know adding this event would create a triple booking.

Using a SortedDict allows us to maintain these change points in chronological order automatically, making it easy to iterate through them and compute the running sum. If we detect a triple booking, we can simply undo our changes by reverting the increments/decrements we just made.

Learn more about Segment Tree, Binary Search and Prefix Sum patterns.

Solution Approach

The solution uses a difference array pattern with a SortedDict data structure to efficiently track booking overlaps.

Data Structure Choice

We use a SortedDict (sorted dictionary) to store time points as keys and their corresponding changes as values. This keeps all time points automatically sorted, which is crucial for our algorithm.

Implementation Details

1. Initialization: Create an empty SortedDict to store the difference array.

2. Booking Process: When book(startTime, endTime) is called:

   • First, optimistically add the new event:
     • self.sd[startTime] = self.sd.get(startTime, 0) + 1 - increment the count at start time
     • self.sd[endTime] = self.sd.get(endTime, 0) - 1 - decrement the count at end time

3. Validation: Check if this creates a triple booking:

   • Initialize a counter s = 0 to track concurrent events
   • Iterate through all values in the SortedDict in chronological order
   • For each time point, add its change value to the running sum: s += v
   • If at any point s > 2, we have detected a triple booking

4. Handling Triple Booking:

   • If triple booking is detected, revert the changes:
     • self.sd[startTime] -= 1 - undo the increment at start time
     • self.sd[endTime] += 1 - undo the decrement at end time
   • Return False to indicate booking failed

5. Successful Booking: If we complete the iteration without finding s > 2, return True

Time Complexity

• Each book operation: O(n) where n is the number of unique time points stored
• The SortedDict maintains order, so insertion is O(log n) but iteration is O(n)

Space Complexity

• O(n) where n is the number of unique time points across all bookings

The elegance of this approach lies in its simplicity - by tracking only the changes at boundary points rather than full intervals, we can efficiently determine the maximum overlap with a single pass through the sorted time points.

Example Walkthrough

Let's walk through a sequence of bookings to see how the difference array approach works:

Initial State: sd = {} (empty SortedDict)

Booking 1: book(10, 20)

1. Add changes: sd[10] = 1, sd[20] = -1
2. SortedDict now: {10: 1, 20: -1}
3. Check for triple booking:
   • Start with s = 0
   • At time 10: s = 0 + 1 = 1 (1 concurrent event) ✓
   • At time 20: s = 1 + (-1) = 0 (0 concurrent events) ✓
4. Maximum concurrent events = 1, no triple booking → Return true

Booking 2: book(15, 25)

1. Add changes: sd[15] = 1, sd[25] = -1
2. SortedDict now: {10: 1, 15: 1, 20: -1, 25: -1}
3. Check for triple booking:
   • Start with s = 0
   • At time 10: s = 0 + 1 = 1 (1 concurrent event) ✓
   • At time 15: s = 1 + 1 = 2 (2 concurrent events) ✓
   • At time 20: s = 2 + (-1) = 1 (1 concurrent event) ✓
   • At time 25: s = 1 + (-1) = 0 (0 concurrent events) ✓
4. Maximum concurrent events = 2, no triple booking → Return true

Booking 3: book(12, 18) (This will overlap with both existing events)

1. Add changes: sd[12] = 1, sd[18] = -1
2. SortedDict now: {10: 1, 12: 1, 15: 1, 18: -1, 20: -1, 25: -1}
3. Check for triple booking:
   • Start with s = 0
   • At time 10: s = 0 + 1 = 1 (1 concurrent event) ✓
   • At time 12: s = 1 + 1 = 2 (2 concurrent events) ✓
   • At time 15: s = 2 + 1 = 3 (3 concurrent events) ✗ Triple booking detected!
4. Revert changes:
   • sd[12] -= 1 → removes the entry (becomes 0)
   • sd[18] += 1 → removes the entry (becomes 0)
5. SortedDict reverts to: {10: 1, 15: 1, 20: -1, 25: -1}
6. Return false

The key insight: Between times 15 and 18, all three events would have overlapped (events [10,20), [15,25), and [12,18)), creating a triple booking. The algorithm detected this when the running sum reached 3 at time 15.

Solution Implementation

Time and Space Complexity

The time complexity is O(n²) where n is the number of bookings.

For each book() operation:

• Adding/updating entries in the SortedDict takes O(log n) time for each operation (two operations: one for startTime and one for endTime)
• Iterating through all values in the SortedDict to check the overlap count takes O(n) time in the worst case, as the dictionary can have up to 2n entries (each booking adds at most 2 entries)
• Since we perform this for each of the n bookings, the total time complexity becomes O(n) * O(n) = O(n²)

The space complexity is O(n) where n is the number of bookings.

The SortedDict stores at most 2n entries (in the worst case, each booking creates two new entries - one for start time and one for end time), which requires O(n) space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Clean Up Zero-Value Entries

The Pitfall: After reverting a failed booking, if you don't remove entries with value 0 from the SortedDict, the dictionary will accumulate unnecessary entries over time. This leads to:

• Increased memory usage
• Slower iteration in future book() calls
• Potential confusion when debugging

Example of the Problem:

# Without cleanup - BAD
if current_bookings > 2:
    self.booking_events[startTime] -= 1
    self.booking_events[endTime] += 1
    # Dictionary might now have {10: 0, 20: 0, ...} entries
    return False

Solution:

# With cleanup - GOOD
if current_bookings > 2:
    self.booking_events[startTime] -= 1
    self.booking_events[endTime] += 1
  
    # Remove zero entries to keep dictionary clean
    if self.booking_events[startTime] == 0:
        del self.booking_events[startTime]
    if self.booking_events[endTime] == 0:
        del self.booking_events[endTime]
  
    return False

2. Using Regular Dict Instead of SortedDict

The Pitfall: Using a regular Python dict will cause incorrect results because the algorithm relies on processing time points in chronological order. Even though Python 3.7+ maintains insertion order, this doesn't help when keys are inserted out of chronological sequence.

Example of the Problem:

# Using regular dict - WRONG
self.booking_events = {}  # Regular dict

# If bookings come in order: book(20, 30), then book(10, 15)
# Dict iteration would be: {20: 1, 30: -1, 10: 1, 15: -1}
# This breaks the chronological scanning logic

Solution:

# Using SortedDict - CORRECT
from sortedcontainers import SortedDict
self.booking_events = SortedDict()

# Now iteration always happens in sorted key order: {10: 1, 15: -1, 20: 1, 30: -1}

3. Incorrect Reversion Logic

The Pitfall: When reverting a failed booking, using the wrong signs for the adjustments. Remember that you need to undo exactly what was done.

Example of the Problem:

# Initial add (correct):
self.booking_events[startTime] = self.booking_events.get(startTime, 0) + 1
self.booking_events[endTime] = self.booking_events.get(endTime, 0) - 1

# Incorrect reversion - WRONG
if current_bookings > 2:
    self.booking_events[startTime] += 1  # Should be -= 1
    self.booking_events[endTime] -= 1     # Should be += 1

Solution:

# Correct reversion
if current_bookings > 2:
    self.booking_events[startTime] -= 1  # Undo the +1
    self.booking_events[endTime] += 1    # Undo the -1

4. Not Using .get() Method for New Keys

The Pitfall: Directly incrementing a key that might not exist in the dictionary will raise a KeyError.

Example of the Problem:

# This will raise KeyError if startTime is not in the dict - WRONG
self.booking_events[startTime] += 1

Solution:

# Use .get() with default value - CORRECT
self.booking_events[startTime] = self.booking_events.get(startTime, 0) + 1

5. Early Return in the Validation Loop

The Pitfall: Returning True as soon as you find a point where current_bookings <= 2, instead of checking all time points.

Example of the Problem:

# WRONG - returns too early
for booking_change in self.booking_events.values():
    current_bookings += booking_change
    if current_bookings <= 2:
        return True  # This is wrong! Need to check ALL points
    if current_bookings > 2:
        # revert and return False

Solution:

# CORRECT - check all points before confirming success
for booking_change in self.booking_events.values():
    current_bookings += booking_change
    if current_bookings > 2:
        # revert and return False
      
# Only return True after checking ALL points
return True