731. My Calendar II

This problem asks to implement a calendar that allows booking events, but prevents triple bookings (where three events overlap). We'll explore two solutions: a Difference Array approach and a Segment Tree approach.

Solution 1: Difference Array

This approach cleverly uses a difference array to track the number of overlapping bookings at each time point. The core idea is:

1. Represent Bookings: Instead of storing the entire event, we only record the change in the number of active bookings at the start and end times. A booking from startTime to endTime is represented by adding 1 at startTime and subtracting 1 at endTime.

2. Difference Array: We use a dictionary (or map) to store these changes. The keys are the start and end times, and the values are the increments (+1) or decrements (-1).

3. Cumulative Sum: We iterate through the sorted keys of the difference array, calculating the cumulative sum. This cumulative sum at any point represents the total number of active bookings at that time.

4. Triple Booking Check: If the cumulative sum ever exceeds 2, it means we have a triple booking, and we reject the new booking.

Time Complexity: O(N log N), where N is the number of bookings. The dominant factor is sorting the keys in the dictionary, which usually takes O(N log N) time. The iteration through the keys takes linear time, O(N).

Space Complexity: O(N), to store the difference array.

Code (Python):

from sortedcontainers import SortedDict
 
class MyCalendarTwo:
    def __init__(self):
        self.diff = SortedDict()
 
    def book(self, startTime: int, endTime: int) -> bool:
        self.diff[startTime] = self.diff.get(startTime, 0) + 1
        self.diff[endTime] = self.diff.get(endTime, 0) - 1
 
        active_bookings = 0
        for count in self.diff.values():
            active_bookings += count
            if active_bookings > 2:
                self.diff[startTime] -= 1
                self.diff[endTime] += 1
                if self.diff[startTime] == 0:
                    del self.diff[startTime]
                if self.diff[endTime] == 0:
                    del self.diff[endTime]
                return False
        return True
 

Other languages (Java, C++, Go, TypeScript, JavaScript) would follow a very similar pattern, using their respective equivalent of a sorted map or dictionary.

Solution 2: Segment Tree

This solution uses a segment tree to efficiently handle overlapping intervals. The segment tree stores the maximum number of bookings within each interval.

1. Segment Tree Structure: A segment tree is a tree data structure where each node represents an interval. The root node represents the entire time range. Each internal node is divided into two subintervals by its left and right children.

2. Bookings as Updates: Adding a booking is done by updating the segment tree to increment the booking count in the corresponding interval.

3. Query for Overlaps: Before adding a booking, we query the segment tree to check the maximum number of bookings within the new booking's interval. If the maximum is already 2, we reject the booking.

Time Complexity: O(N log M), where N is the number of bookings and M is the range of time (109 in this case). Each book operation takes O(log M) time for the segment tree update and query.

Space Complexity: O(M) in the worst case to store the segment tree, where M is the total range of the time values. However, for this specific problem, dynamic segment trees can reduce space complexity significantly.

Code (Python): (Note: This is a simplified example. A fully optimized segment tree implementation for a large range like 109 would typically use a more sophisticated dynamic node allocation strategy to avoid excessive memory consumption).

class Node:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.count = 0
        self.left = None
        self.right = None
 
class SegmentTree:
    def __init__(self):
        self.root = Node(0, 10**9)  # Adjust range as needed
 
    def update(self, start, end, node):
        if node.start == node.end:
            node.count += 1
            return
 
        mid = (node.start + node.end) // 2
        if start <= mid:
            if not node.left:
                node.left = Node(node.start, mid)
            self.update(start, end, node.left)
        if end > mid:
            if not node.right:
                node.right = Node(mid + 1, node.end)
            self.update(start, end, node.right)
        node.count = max(node.left.count, node.right.count)
 
 
    def query(self, start, end, node):
        if start > node.end or end < node.start:
            return 0
        if start <= node.start and end >= node.end:
            return node.count
        mid = (node.start + node.end) // 2
        left_count = 0 if not node.left else self.query(start, end, node.left)
        right_count = 0 if not node.right else self.query(start, end, node.right)
        return max(left_count, right_count)
 
 
class MyCalendarTwo:
    def __init__(self):
        self.tree = SegmentTree()
 
    def book(self, start: int, end: int) -> bool:
        if self.tree.query(start, end-1, self.tree.root) >= 2:
            return False
        self.tree.update(start, end-1, self.tree.root)
        return True
 

The Segment Tree solution offers better scalability for a very large time range, though it's more complex to implement. The Difference Array is simpler but may be less efficient for extremely large numbers of bookings. The choice depends on the expected scale of the input.