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.


&nbsp;
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, 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


&nbsp;
Constraints:


	0 &lt;= start &lt; end &lt;= 109
	At most 400 calls will be made to book.


import bisect
class MyCalendarThree:

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

    def book(self, start: int, end: int) -> int:
        L, R = 1, 0
        bisect.insort(self.events, (start, L))
        bisect.insort(self.events, (end, R))
        res = 0
        cnt = 0
        for _, state in self.events:
            #if an interval starts, increase the counter
            #othewise, decreas the counter
            cnt += 1 if state == L else -1
            res = max(res, cnt)
        return res
class MyCalendarThree {

    TreeMap<Integer, Integer> map;
    public MyCalendarThree() {
        map = new TreeMap<>();
    }

    public int book(int start, int end) {
        if(map.isEmpty()){
            map.put(start, 1);
            map.put(end,-1);
            return 1;
        }

        //upvote if you like the solution

        map.put(start, map.getOrDefault(start,0)+1);
        map.put(end, map.getOrDefault(end,0)-1);

        int res = 0;
        int sum = 0;
        for(Map.Entry<Integer, Integer> e: map.entrySet()){
            sum += e.getValue();
            res = Math.max(res,sum);
        }

        return res;
    }
}
class MyCalendarThree {
public:
    map<int,int>mp;
    MyCalendarThree() {   
    }
    int book(int start, int end) {
        mp[start]++;
        mp[end]--;
        int sum = 0;
        int ans = 0;
        for(auto it = mp.begin(); it != mp.end(); it++){
            sum += it->second;
            ans = max(ans,sum);
        }
        return ans;
    }
};
var MyCalendarThree = function() {
    this.intersections = [];
    this.kEvents = 0;
    
};

/** 
 * @param {number} start 
 * @param {number} end
 * @return {number}
 */
MyCalendarThree.prototype.book = function(start, end) {
    let added = false;
    for(let i = 0; i < this.intersections.length; i++) {
        const a = this.intersections[i];
        if(end <= a.start) {
            this.intersections.splice(i, 0, {start, end, count: 1});
            this.kEvents = Math.max(this.kEvents, 1);
            this.added = true;
            break;
        }
        if(start < a. start) {
            this.intersections.splice(i, 0, {start, end: a.start, count: 1});
            i++;
            start = a.start;
        }
        if(a.start < start && start < a.end ) {
            this.intersections.splice(i, 0, {start: a.start, end: start, count: a.count});
            i++;
            a.start = start;
        }
        if(end < a.end) {
            this.intersections.splice(i + 1, 0, {start: end, end: a.end, count: a.count});
            a.count++;
            a.end = end;
            this.kEvents = Math.max(this.kEvents, a.count);
            this.added = true;
            break;
        }
        if(end === a.end) {
            a.count++;
            a.end = end;
            this.kEvents = Math.max(this.kEvents, a.count); 
            this.added = true;
            break;
        } 
        if(a.start === start && a.end < end ) {
            a.count++;
            this.kEvents = Math.max(this.kEvents, a.count);
            start = a.end;
        }
    }
    if(!added) {
        this.intersections.push({start, end, count: 1});
        this.kEvents = Math.max(this.kEvents, 1);
    }
    return this.kEvents;
};
My Calendar III