# 732. My Calendar III

#### Hard

***

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 `[start, end)`, 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 start, int end)` Returns an integer `k` representing the largest integer such that there exists a `k`-booking in the calendar.

 

**Example 1:**

<pre><code>Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
<strong>Output
</strong>[null, 1, 1, 2, 3, 3, 3]
<strong>Explanation
</strong>MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1, The first event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarThree.book(50, 60); // return 1, The second event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarThree.book(10, 40); // return 2, The third event [10, 40) intersects the first event, and the maximum k-booking is a 2-booking.
myCalendarThree.book(5, 15); // return 3, The remaining events cause the maximum K-booking to be only a 3-booking.
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3
</code></pre>

&#x20;

**Constraints:**

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

```python
class Node:
    def __init__(self, start, end, time=1):
        self.start = start
        self.end = end
        self.left = None
        self.right = None
        self.time = time
class MyCalendarThree:

    def __init__(self):
        self.root = None
        self.k = 0
        

    def book(self, start: int, end: int) -> int:
        self.root = self.helper(self.root, start, end, 1)
        return self.k
    
    def helper(self, root, start, end, time):
        if start >= end:
            return root
        if not root:
            self.k = max(self.k, time)
            return Node(start, end, time)
        else:
            if start >= root.end:
                root.right = self.helper(root.right, start, end, time)
            elif end <= root.start:    
                root.left = self.helper(root.left, start, end, time)
            else:
                a = min(root.start, start)
                b = max(root.start, start)
                c = min(root.end, end)
                d = max(root.end, end)
                
                root.left = self.helper(root.left, a, b, root.time if a == root.start else time)
                root.right = self.helper(root.right, c, d, root. time if d == root.end else time)
                
                root.time += time
                root.start = b
                root.end = c
                self.k = max(self.k, root.time)
            return root
```