## Algorithm

Problem Name: 732. My Calendar III

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`.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class MyCalendarThree {

private TreeMap delta;

public MyCalendarThree() {
this.delta = new TreeMap<>();
}

public int book(int start, int end) {
delta.put(start, delta.getOrDefault(start, 0) + 1);
delta.put(end, delta.getOrDefault(end, 0) - 1);
int activeEvents = 0;
int maxEvents = 0;
for (int d : delta.values()) {
activeEvents += d;
maxEvents = Math.max(maxEvents, activeEvents);
}
return maxEvents;
}
}
``````
Copy The Code &

Input

cmd
["MyCalendarThree", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

Output

cmd
[null, 1, 1, 2, 3, 3, 3]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const find = (cals, time, count) => {
let l = 0
let r = cals.length
let mid
while (l < r) {
mid = Math.trunc((l + r) / 2)
if (cals[mid] === time) {
cals[mid] += count
return
} else if (cals[mid] < time) {
l = mid + 1
} else {
r = mid
}
}
cals.splice(l, 0, [time, count])
}
const MyCalendarThree = function() {
this.cals = []
}

MyCalendarThree.prototype.book = function(start, end) {
let idx = find(this.cals, start, 1)
idx = find(this.cals, end, -1)
let count = 0
let max = 0
for (let cal of this.cals) {
count += cal
max = Math.max(max, count)
}
return max
}
``````
Copy The Code &

Input

cmd
["MyCalendarThree", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

Output

cmd
[null, 1, 1, 2, 3, 3, 3]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class MyCalendarThree:

def __init__(self):
self.times = []

def book(self, start, end):
bisect.insort(self.times, (start, 1))
bisect.insort(self.times, (end, -1))
res = cur = 0
for _, x in self.times:
cur += x
res = max(res, cur)
return res
``````
Copy The Code &

Input

cmd
["MyCalendarThree", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

Output

cmd
[null, 1, 1, 2, 3, 3, 3]