{x}
blog image

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.

Solution Explanation: My Calendar III

This problem requires designing a data structure that efficiently tracks overlapping intervals and returns the maximum k-booking (the maximum number of overlapping intervals at any point in time). A segment tree is an excellent choice for this because it allows for efficient querying of range maxima and updates.

Approach:

We use a segment tree to represent the time intervals. Each node in the tree represents a range of time, and stores the maximum number of bookings within that range. When a new booking [startTime, endTime) is added:

  1. Update the Segment Tree: We traverse the segment tree, updating the v (value) of nodes that fall within the booking's range. The v represents the number of bookings overlapping in that segment. We use add for lazy propagation to avoid redundant updates.
  2. Query the Segment Tree: After updating, we query the entire segment tree to find the maximum value of v across all ranges. This maximum value represents the maximum k-booking.

Data Structures:

  • Node: Represents a node in the segment tree. It contains:

    • left, right: Pointers to child nodes.
    • l, r: The start and end times of the range represented by the node.
    • mid: The midpoint of the range.
    • v: The maximum number of bookings overlapping within the range.
    • add: A lazy propagation marker to efficiently update ranges.

  • SegmentTree: Manages the segment tree. It includes methods for:

    • modify: Updates the tree with a new booking.
    • query: Queries the tree for the maximum k-booking.
    • pushup: Updates the v value of a node based on its children's values.
    • pushdown: Propagates the add value down the tree.

  • MyCalendarThree: The main class that interacts with the segment tree. It uses the SegmentTree to handle booking requests.

Time and Space Complexity:

  • Time Complexity: The book operation involves traversing a path in the segment tree, which has a height of O(log N), where N is the range of time (in this case, effectively 109, though we use dynamic nodes). Therefore, the time complexity of each book operation is O(log N). Since there are at most 400 calls to book, the overall time complexity is O(M log N), where M is the number of booking calls (at most 400).

  • Space Complexity: The space complexity is determined by the number of nodes in the segment tree. In the worst case, the tree could have approximately 400 nodes (one for each booking), although the actual number is much less due to overlapping intervals and the efficient use of dynamic node creation. Thus, the space complexity is O(M), where M is the number of bookings. However, in terms of Big O, it's considered O(N) in relation to the input space. This is because the tree grows dynamically to accomodate the bookings.

The provided code demonstrates the implementation of this approach in Python, Java, C++, Go, and TypeScript. The core logic remains consistent across all languages, with minor syntactic differences. The use of lazy propagation in the pushdown function is crucial for maintaining the efficiency of the segment tree.