#732

My Calendar III

specialist · 985 · lc hard +32 · 71.5% accepted · 2,082 likes · top 80%

⚑ Segment Tree (Range Query + Update)⚑ Sweep Line

Description

A k-booking occurs when k events share a common non-empty time interval. Design a calendar that accepts all events and, after each booking, reports the largest k such that a k-booking currently exists.

Implement the MyCalendarThree class:

- MyCalendarThree() Creates the calendar.

- int book(int startTime, int endTime) Records the event [startTime, endTime) and returns the maximum concurrency level k across all bookings so far.

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]

Example 2:

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

Code

class MyCalendarThree:

    def __init__(self):
        

    def book(self, startTime: int, endTime: int) -> int:
        


# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(startTime,endTime)

class MyCalendarThree:

    def __init__(self):
        

    def book(self, startTime: int, endTime: int) -> int:
        


# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(startTime,endTime)