My Calendar II

XXX. My Calendar II (Double Booking)

TreeMap

Prefix Sum

Problem Statement:

Implement a calendar class that allows for double booking but prevents triple booking. A triple booking occurs when three or more events overlap.

• Allow at most two overlapping events
• Return false for third overlapping booking
• Events are half-open intervals [start, end)

Implementation:

class MyCalendarTwo {
    private TreeMap bookingCount;  // Track event boundaries
    private int maxOverlappedBooking;               // Maximum allowed overlaps
    
    public MyCalendarTwo() {
        bookingCount = new TreeMap<>();
        maxOverlappedBooking = 2;                   // Allow double booking
    }
    
    public boolean book(int start, int end) {
        // Add boundary counts (+1 at start, -1 at end)
        bookingCount.put(start, bookingCount.getOrDefault(start, 0) + 1);
        bookingCount.put(end, bookingCount.getOrDefault(end, 0) - 1);
        
        int overlappedBooking = 0;
        // Calculate prefix sum to find overlaps
        for (Map.Entry entry : bookingCount.entrySet()) {
            overlappedBooking += entry.getValue();
            
            // Check if triple booking would occur
            if (overlappedBooking > maxOverlappedBooking) {
                // Rollback the changes
                bookingCount.put(start, bookingCount.get(start) - 1);
                bookingCount.put(end, bookingCount.get(end) + 1);
                
                // Clean up zero counts
                if (bookingCount.get(start) == 0) {
                    bookingCount.remove(start);
                }
                return false;
            }
        }
        return true;
    }
}

Complexity:

Time Complexity: O(n) for each booking, where n is number of bookings
Space Complexity: O(n) to store all event boundaries

Key Points:

• **TreeMap Usage**:
  • Automatically sorts time points
  • Stores boundary counts (+1/-1)
  • Enables ordered traversal for prefix sum
• **Boundary Count Technique**:
  • +1 at event start
  • -1 at event end
  • Running sum shows current overlaps
• **Rollback Mechanism**:
  • Revert changes on triple booking
  • Clean up zero count entries
  • Maintains map consistency

Example:

For bookings: [10,20], [15,25], [20,30]

• After booking [10,20]:
  • Map: {10:+1, 20:-1}
  • Max overlap: 1
• After booking [15,25]:
  • Map: {10:+1, 15:+1, 20:-1, 25:-1}
  • Max overlap: 2
• Success: No triple booking occurs

Implementation Notes:

• **Memory Management**:
  • Remove zero count entries
  • Prevents map growth with cancellations
  • Maintains minimal memory usage
• **Error Prevention**:
  • Check overlaps before committing
  • Complete rollback on failure
  • Maintain consistent state