# My Calendar III
**Difficulty:** HARD
[External](https://leetcode.com/problems/my-calendar-iii)
Canonical: https://scaleengineer.com/dsa/problems/my-calendar-iii
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Segment Tree, Ordered Set
---
## Problem
A `k`\-booking happens when `k` events have some non-empty intersection (i.e., there is some time that is common to all `k` events.)

You are given some events `[startTime, endTime)`, after each given event, return an integer `k` representing the maximum `k`\-booking between all the previous events.

Implement the `MyCalendarThree` class:

* `MyCalendarThree()` Initializes the object.
* `int book(int startTime, int endTime)` Returns an integer `k` representing the largest integer such that there exists a `k`\-booking in the calendar.

**Example 1:**

**Input**
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
**Output**
[null, 1, 1, 2, 3, 3, 3]

**Explanation**
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15); // return 3
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3

**Constraints:**

* `0 <= startTime < endTime <= 109`
* At most `400` calls will be made to `book`.

# Approaches
## Brute Force with Endpoint Iteration
This approach involves storing all events and, for each `book` call, recalculating the maximum overlap from scratch. We identify all unique start and end times (endpoints) from the booked events. The maximum overlap must occur at one of these start times. Therefore, we can iterate through each unique endpoint and count how many intervals are active at that specific moment. The highest count we find is the maximum k-booking.
**Time:** O(N^2) per `book` call. After N calls, there are N events and at most 2N unique endpoints. Iterating through O(N) points and for each point, iterating through N events results in O(N^2) complexity. · **Space:** O(N), where N is the number of calls to `book`. We need to store N events, and there are at most 2N unique endpoints.
**Pros:** Simple to understand and implement.; Requires minimal data structures, just a list and a set.
**Cons:** The time complexity of O(N^2) per `book` call makes it inefficient, especially as the number of events `N` grows.; The total time complexity over all calls can be up to O(N^3), which might be too slow and lead to a 'Time Limit Exceeded' error in a competitive programming context.
### Explanation
In this brute-force method, we maintain a simple list of all the event intervals that have been booked. When a new `book(start, end)` request comes in, we first add the new interval `[start, end)` to our list.

The core idea is that the number of concurrent events, or overlaps, can only change at the start or end time of an event. Therefore, to find the maximum number of overlaps, we only need to check these specific time points. We gather all unique start and end times from our list of events into a collection, for instance, a `TreeSet` to keep them sorted and unique.

Then, we iterate through each of these unique time points. For each point, we scan through our entire list of booked events and count how many of them contain this point. The maximum count found during this process is the maximum k-booking for the current set of events. While simple to grasp, this method is computationally expensive because it re-evaluates all events and all critical points for every single `book` call.

```java
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

class MyCalendarThree {
    private List<int[]> books;

    public MyCalendarThree() {
        books = new ArrayList<>();
    }

    public int book(int startTime, int endTime) {
        books.add(new int[]{startTime, endTime});
        
        Set<Integer> points = new TreeSet<>();
        for (int[] b : books) {
            points.add(b[0]);
            // We only need to check start points, as the overlap count
            // is constant between any two consecutive endpoints.
        }
        
        int maxK = 0;
        if (books.isEmpty()) {
            return 0;
        }
        
        // The maximum overlap will occur at some event's start time.
        for (int point : points) {
            int currentK = 0;
            for (int[] b : books) {
                if (b[0] <= point && point < b[1]) {
                    currentK++;
                }
            }
            maxK = Math.max(maxK, currentK);
        }
        
        return maxK;
    }
}
```
### Algorithm
- Maintain a list of all booked events.
- For each `book` call, add the new event to the list.
- To find the maximum k-booking, create a set of all unique start and end times from the list of events. These are the critical points where the number of overlapping events can change.
- Iterate through each unique point `p`.
- For each point `p`, iterate through all the booked events and count how many of them are active at time `p` (i.e., `event.start <= p < event.end`).
- Keep track of the maximum count found across all points. This maximum count is the result.

## Boundary Counting with Sorted Map
This approach, often called Boundary Counting or Difference Array, is based on a key insight: the number of overlapping events only changes at the start and end times of the intervals. We can think of a `startTime` as an event that increases the overlap count by one, and an `endTime` as an event that decreases it by one. By processing these `+1` and `-1` changes in chronological order, we can find the maximum overlap at any point in time. A sorted map, like Java's `TreeMap`, is ideal for storing these time points and their associated changes, as it automatically keeps them in sorted order.
**Time:** O(N) per `book` call. Each `book` call involves two O(log N) operations on the `TreeMap` for updates. The subsequent sweep through the map takes O(N) time as there are at most 2N entries. The linear scan dominates the complexity. · **Space:** O(N), where N is the number of calls to `book`. The `TreeMap` will store at most 2N distinct endpoints.
**Pros:** Significantly more efficient than the brute-force approach.; Conceptually elegant and a common technique for interval-based problems.; The state (the timeline) is updated incrementally, avoiding recalculation.
**Cons:** While much better than brute force, it still requires a linear scan through all distinct endpoints for each `book` call, which could be optimized further.
### Explanation
Instead of re-calculating from scratch every time, we can maintain a data structure that tracks the net change of events at each endpoint. A `TreeMap` is perfect for this, mapping time points to the change in the number of active events.

For each call to `book(start, end)`:
1.  We record that at `startTime`, one new event begins. We do this by incrementing the value associated with the key `start` in our `TreeMap`. `timeline.put(start, timeline.getOrDefault(start, 0) + 1);`
2.  Similarly, at `endTime`, one event concludes. We record this by decrementing the value for the key `end`. `timeline.put(end, timeline.getOrDefault(end, 0) - 1);`

After updating the map for the new event, we can determine the maximum number of concurrent events. Since the `TreeMap` keeps the keys (time points) sorted, we can iterate through its values in chronological order. We maintain a running count of active events. By sweeping through the timeline, we add each change to our running count. The peak value this running count reaches is the maximum k-booking.

```java
import java.util.TreeMap;

class MyCalendarThree {
    private TreeMap<Integer, Integer> timeline;

    public MyCalendarThree() {
        timeline = new TreeMap<>();
    }

    public int book(int startTime, int endTime) {
        // +1 for a new event starting
        timeline.put(startTime, timeline.getOrDefault(startTime, 0) + 1);
        // -1 for an event ending
        timeline.put(endTime, timeline.getOrDefault(endTime, 0) - 1);

        int maxK = 0;
        int currentK = 0;
        // Sweep through the timeline to find the max overlap
        for (int count : timeline.values()) {
            currentK += count;
            maxK = Math.max(maxK, currentK);
        }
        return maxK;
    }
}
```
### Algorithm
- Use a `TreeMap` to store the changes in the number of active events at specific time points. The keys of the map are the time points, and the values are the net change (+1 for a start, -1 for an end).
- For each `book(start, end)` call:
  - Increment the value at key `start` by 1. If the key doesn't exist, it's equivalent to setting it to 1.
  - Decrement the value at key `end` by 1. This marks the end of the interval.
- To find the maximum k-booking, iterate through the values of the `TreeMap` (which are naturally sorted by time).
- Maintain a running sum of the active events (`currentK`) and a maximum sum (`maxK`).
- As you iterate, add the value (the change) to `currentK` and update `maxK = max(maxK, currentK)`.
- The final `maxK` is the answer.

## Dynamic Segment Tree with Lazy Propagation
The most efficient solution utilizes a Segment Tree with Lazy Propagation. This data structure is designed for handling range updates and range queries efficiently. Each `book(start, end)` call corresponds to incrementing all values in the range `[start, end-1]` by one. The maximum k-booking is then the maximum value over the entire range. To handle the large coordinate space (0 to 10^9), we use a dynamic or implicit segment tree, where nodes are created on-the-fly as they are accessed, avoiding the need to pre-allocate a massive tree.
**Time:** O(log C) per `book` call. Each update on the segment tree traverses a path from the root, taking logarithmic time relative to the size of the coordinate range C. · **Space:** O(N * log C), where N is the number of `book` calls and C is the maximum coordinate value (10^9). Each update can create O(log C) new nodes.
**Pros:** Extremely efficient time complexity per operation.; This is the optimal approach for this type of problem (range updates, max query).; Scales well even if the number of `book` calls were much larger.
**Cons:** Implementation is significantly more complex than the other approaches.; The space complexity, while manageable for the given constraints, depends on both the number of calls `N` and the logarithm of the coordinate range `C`.
### Explanation
A Segment Tree is a powerful tree data structure that allows for efficient range queries and updates. In our case, a `book(start, end)` operation is an update on the range `[start, end-1]` (incrementing by 1), and we need to find the maximum value in the entire tree after each update.

The challenge is the vast range of time coordinates (`0` to `10^9`). A standard segment tree would require an array of an impossible size. The solution is a **Dynamic Segment Tree**, where each node is an object with pointers to its left and right children, which are initially null. A node is created only when a query or update needs to traverse to it.

To make range updates efficient, we use **lazy propagation**. When an update range completely covers a node's interval, we don't update all its descendant leaves. Instead, we store a `lazy` value at that node (e.g., `+1`) and update its `maxVal`. This `lazy` value is 'pushed down' to its children only when we need to traverse past this node in a future operation.

For each `book(start, end)` call, we call an `update` function on our segment tree. After the `O(log C)` update operation is complete, the `maxVal` stored at the root of the tree gives us the global maximum k-booking.

```java
class MyCalendarThree {
    private static class Node {
        int maxVal;
        int lazy;
        Node left, right;

        Node() {
            this.maxVal = 0;
            this.lazy = 0;
            this.left = null;
            this.right = null;
        }
    }

    private Node root;
    private final int MAX_COORD = 1_000_000_000;

    public MyCalendarThree() {
        root = new Node();
    }

    public int book(int startTime, int endTime) {
        // The interval is [startTime, endTime), so we update up to endTime - 1.
        update(root, 0, MAX_COORD, startTime, endTime - 1);
        return root.maxVal;
    }

    private void push(Node node) {
        if (node.lazy > 0) {
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            
            node.left.lazy += node.lazy;
            node.left.maxVal += node.lazy;
            node.right.lazy += node.lazy;
            node.right.maxVal += node.lazy;
            
            node.lazy = 0;
        }
    }

    private void update(Node node, int nodeL, int nodeR, int queryL, int queryR) {
        // Full overlap: update lazy tag and max value, then return.
        if (queryL <= nodeL && nodeR <= queryR) {
            node.lazy += 1;
            node.maxVal += 1;
            return;
        }

        // Before recursing, push down lazy values.
        push(node);
        
        int mid = nodeL + (nodeR - nodeL) / 2;
        
        // Recurse on children based on overlap.
        if (queryL <= mid) {
            if (node.left == null) node.left = new Node();
            update(node.left, nodeL, mid, queryL, queryR);
        }
        if (queryR > mid) {
            if (node.right == null) node.right = new Node();
            update(node.right, mid + 1, nodeR, queryL, queryR);
        }

        // After children are updated, pull their max value up.
        int leftMax = (node.left != null) ? node.left.maxVal : 0;
        int rightMax = (node.right != null) ? node.right.maxVal : 0;
        node.maxVal = Math.max(leftMax, rightMax);
    }
}
```
### Algorithm
- The problem can be modeled as range updates and a global max query. A Segment Tree is a suitable data structure for this.
- Since the time coordinates can be very large (up to 10^9), a standard array-based segment tree is not feasible. We use a **Dynamic Segment Tree** (or Implicit Segment Tree), where nodes are created only when needed.
- Each node in the tree represents a time interval and stores `maxVal` (the max k-booking in its range) and a `lazy` tag for pending updates.
- For each `book(start, end)` call, we perform a range update on the segment tree for the interval `[start, end-1]`, incrementing the count by 1.
- The update operation uses **lazy propagation**. When an update fully covers a node's range, we update its `lazy` tag and `maxVal` and stop descending. For partial overlaps, we first push the lazy value down to children and then recurse.
- After each update, the `maxVal` of the root node will hold the maximum k-booking over the entire timeline.

# Solutions
### Java

```java
class Node { Node left ; Node right ; int l ; int r ; int mid ; int v ; int add ; public Node ( int l , int r ) { this . l = l ; this . r = r ; this . mid = ( l + r ) >> 1 ; } } class SegmentTree { private Node root = new Node ( 1 , ( int ) 1 e9 + 1 ); public SegmentTree () { } public void modify ( int l , int r , int v ) { modify ( l , r , v , root ); } public void modify ( int l , int r , int v , Node node ) { if ( l > r ) { return ; } if ( node . l >= l && node . r <= r ) { node . v += v ; node . add += v ; return ; } pushdown ( node ); if ( l <= node . mid ) { modify ( l , r , v , node . left ); } if ( r > node . mid ) { modify ( l , r , v , node . right ); } pushup ( node ); } public int query ( int l , int r ) { return query ( l , r , root ); } public int query ( int l , int r , Node node ) { if ( l > r ) { return 0 ; } if ( node . l >= l && node . r <= r ) { return node . v ; } pushdown ( node ); int v = 0 ; if ( l <= node . mid ) { v = Math . max ( v , query ( l , r , node . left )); } if ( r > node . mid ) { v = Math . max ( v , query ( l , r , node . right )); } return v ; } public void pushup ( Node node ) { node . v = Math . max ( node . left . v , node . right . v ); } public void pushdown ( Node node ) { if ( node . left == null ) { node . left = new Node ( node . l , node . mid ); } if ( node . right == null ) { node . right = new Node ( node . mid + 1 , node . r ); } if ( node . add != 0 ) { Node left = node . left , right = node . right ; left . add += node . add ; right . add += node . add ; left . v += node . add ; right . v += node . add ; node . add = 0 ; } } } class MyCalendarThree { private SegmentTree tree = new SegmentTree (); public MyCalendarThree () { } public int book ( int start , int end ) { tree . modify ( start + 1 , end , 1 ); return tree . query ( 1 , ( int ) 1 e9 + 1 ); } } /** * Your MyCalendarThree object will be instantiated and called as such: * MyCalendarThree obj = new MyCalendarThree(); * int param_1 = obj.book(start,end); */
```

### CPP

```cpp
class Node { public: Node * left ; Node * right ; int l ; int r ; int mid ; int v ; int add ; Node ( int l , int r ) { this -> l = l ; this -> r = r ; this -> mid = ( l + r ) >> 1 ; this -> left = this -> right = nullptr ; v = add = 0 ; } }; class SegmentTree { private: Node * root ; public: SegmentTree () { root = new Node ( 1 , 1e9 + 1 ); } void modify ( int l , int r , int v ) { modify ( l , r , v , root ); } void modify ( int l , int r , int v , Node * node ) { if ( l > r ) return ; if ( node -> l >= l && node -> r <= r ) { node -> v += v ; node -> add += v ; return ; } pushdown ( node ); if ( l <= node -> mid ) modify ( l , r , v , node -> left ); if ( r > node -> mid ) modify ( l , r , v , node -> right ); pushup ( node ); } int query ( int l , int r ) { return query ( l , r , root ); } int query ( int l , int r , Node * node ) { if ( l > r ) return 0 ; if ( node -> l >= l && node -> r <= r ) return node -> v ; pushdown ( node ); int v = 0 ; if ( l <= node -> mid ) v = max ( v , query ( l , r , node -> left )); if ( r > node -> mid ) v = max ( v , query ( l , r , node -> right )); return v ; } void pushup ( Node * node ) { node -> v = max ( node -> left -> v , node -> right -> v ); } void pushdown ( Node * node ) { if ( ! node -> left ) node -> left = new Node ( node -> l , node -> mid ); if ( ! node -> right ) node -> right = new Node ( node -> mid + 1 , node -> r ); if ( node -> add ) { Node * left = node -> left ; Node * right = node -> right ; left -> v += node -> add ; right -> v += node -> add ; left -> add += node -> add ; right -> add += node -> add ; node -> add = 0 ; } } }; class MyCalendarThree { public: SegmentTree * tree ; MyCalendarThree () { tree = new SegmentTree (); } int book ( int start , int end ) { tree -> modify ( start + 1 , end , 1 ); return tree -> query ( 1 , 1e9 + 1 ); } }; /** * Your MyCalendarThree object will be instantiated and called as such: * MyCalendarThree* obj = new MyCalendarThree(); * int param_1 = obj->book(start,end); */
```

### Python

```python
from sortedcontainers import SortedDict class MyCalendarThree : def __init__ ( self ): self . timeline = SortedDict () def book ( self , start : int , end : int ) -> int : self . timeline [ start ] = self . timeline . get ( start , 0 ) + 1 self . timeline [ end ] = self . timeline . get ( end , 0 ) - 1 return max ( accumulate ( list ( self . timeline . values ()))) ############ class Node : def __init__ ( self , l , r ): self . left = None self . right = None self . l = l self . r = r self . mid = ( l + r ) >> 1 self . v = 0 self . add = 0 class SegmentTree : # <=== def __init__ ( self ): self . root = Node ( 1 , int ( 1e9 + 1 )) def modify ( self , l , r , v , node = None ): if l > r : return if node is None : node = self . root if node . l >= l and node . r <= r : node . v += v node . add += v return self . pushdown ( node ) if l <= node . mid : self . modify ( l , r , v , node . left ) if r > node . mid : self . modify ( l , r , v , node . right ) self . pushup ( node ) def query ( self , l , r , node = None ): if l > r : return 0 if node is None : node = self . root if node . l >= l and node . r <= r : return node . v self . pushdown ( node ) v = 0 if l <= node . mid : v = max ( v , self . query ( l , r , node . left )) if r > node . mid : v = max ( v , self . query ( l , r , node . right )) return v def pushup ( self , node ): node . v = max ( node . left . v , node . right . v ) def pushdown ( self , node ): if node . left is None : node . left = Node ( node . l , node . mid ) if node . right is None : node . right = Node ( node . mid + 1 , node . r ) if node . add : node . left . v += node . add node . right . v += node . add node . left . add += node . add node . right . add += node . add node . add = 0 class MyCalendarThree : def __init__ ( self ): self . tree = SegmentTree () def book ( self , start : int , end : int ) -> int : self . tree . modify ( start + 1 , end , 1 ) return self . tree . query ( 1 , int ( 1e9 + 1 )) # Your MyCalendarThree object will be instantiated and called as such: # obj = MyCalendarThree() # param_1 = obj.book(start,end) ############ class Node ( object ): def __init__ ( self , start , end , c ): self . start = start self . end = end self . count = c self . left = None self . right = None class MyCalendarThree ( object ): def __init__ ( self ): self . root = None self . maxK = 1 def book_helper ( self , root , start , end , c ): if root == None : return Node ( start , end , c ) if start >= root . end : #不能写成return self.boook_helper()，因为要进行树的构建和修改，一定要赋值给root.right root . right = self . book_helper ( root . right , start , end , c ) elif end <= root . start : root . left = self . book_helper ( root . left , start , end , c ) else : intervals = sorted ([ start , end , root . start , root . end ]) root_l , root_r = root . start , root . end root . start , root . end = intervals [ 1 ], intervals [ 2 ] root . left = self . book_helper ( root . left , intervals [ 0 ], intervals [ 1 ], c if start <= root_l else root . count ) root . right = self . book_helper ( root . right , intervals [ 2 ], intervals [ 3 ], c if end >= root_r else root . count ) root . count += c self . maxK = max ( root . count , self . maxK ) return root def book ( self , start , end ): """ :type start: int :type end: int :rtype: int """ self . root = self . book_helper ( self . root , start , end , 1 ) return self . maxK # Your MyCalendarThree object will be instantiated and called as such: # obj = MyCalendarThree() # param_1 = obj.book(start,end)
```