# 732. My Calendar III

不断插入range，实时问当前最大的overlap数目。题目需求和Range Module类似，也是不断加range然后做query。不同的是这道题要求统计overlap，所以不能合并overlap。最直接的做法就是排序+1-1，维持动态排序用tree map。优化的话用类似Range Module思路，二分法定位到与input overlap的ranges，然后针对这些ranges做统计。但map中存的不能是range，而是一个个点和点对应的高度，line sweep思想，遍历到某点意味着进入该点开始高度变为h，像俄罗斯方块：

![](https://pic1.zhimg.com/v2-545af77672e030048f180f4ac9b569a4_b.png)

用二分法找出涵盖了整个\[start, end]的边界\[l, r]。遍历l->r, \[start, end)内的所有点高度+1。end时说明进入了新的一段，高度还原成cur->second且不能加+1。遍历时如果map中原先没有start和end就创建，并让他们高度等于当前cur->second。图片和解法来自[花花](https://www.youtube.com/watch?v=yK9a-rT3FBQ)。

```cpp
/*
 * @lc app=leetcode id=732 lang=cpp
 *
 * [732] My Calendar III
 *
 * https://leetcode.com/problems/my-calendar-iii/description/
 *
 * algorithms
 * Hard (56.53%)
 * Likes:    260
 * Dislikes: 90
 * Total Accepted:    15.2K
 * Total Submissions: 26.8K
 * Testcase Example:  '["MyCalendarThree","book","book","book","book","book","book"]\n[[],[10,20],[50,60],[10,40],[5,15],[5,10],[25,55]]'
 *
 * Implement a MyCalendarThree class to store your events. A new event can
 * always be added.
 * 
 * Your class will have one method, book(int start, int end). Formally, this
 * represents a booking on the half open interval [start, end), the range of
 * real numbers x such that start <= x < end.
 * 
 * A K-booking happens when K events have some non-empty intersection (ie.,
 * there is some time that is common to all K events.)
 * 
 * For each call to the method MyCalendar.book, return an integer K
 * representing the largest integer such that there exists a K-booking in the
 * calendar.
 * Your class will be called like this: MyCalendarThree cal = new
 * MyCalendarThree(); MyCalendarThree.book(start, end)
 * 
 * Example 1:
 * 
 * 
 * MyCalendarThree();
 * MyCalendarThree.book(10, 20); // returns 1
 * MyCalendarThree.book(50, 60); // returns 1
 * MyCalendarThree.book(10, 40); // returns 2
 * MyCalendarThree.book(5, 15); // returns 3
 * MyCalendarThree.book(5, 10); // returns 3
 * MyCalendarThree.book(25, 55); // returns 3
 * Explanation: 
 * The first two events can be booked and are disjoint, so the maximum
 * K-booking is a 1-booking.
 * The third event [10, 40) intersects the first event, and the maximum
 * K-booking is a 2-booking.
 * The remaining events cause the maximum K-booking to be only a 3-booking.
 * Note that the last event locally causes a 2-booking, but the answer is still
 * 3 because
 * eg. [10, 20), [10, 40), and [5, 15) are still triple booked.
 * 
 * 
 * 
 * 
 * Note:
 * 
 * 
 * The number of calls to MyCalendarThree.book per test case will be at most
 * 400.
 * In calls to MyCalendarThree.book(start, end), start and end are integers in
 * the range [0, 10^9].
 * 
 * 
 * 
 */

// @lc code=start
class MyCalendarThree {
public:
    map<int, int> heights;
    typedef map<int, int>::iterator IT;
    int max_c;

    MyCalendarThree() {
        heights[INT_MAX] = 0;
        heights[INT_MIN] = 0;
        max_c = 0;
    }
    
    int book(int start, int end) {
        IT l, r;
        // [l, r]: l.start <= start, r.start >= end
        l = prev(heights.upper_bound(start));
        r = heights.lower_bound(end);
        // [cur, next]表示一个区间
        for (auto cur = l, nxt = next(cur); cur != r; cur = nxt, ++nxt) {
            // 区间遍历结束
            if (nxt->first > end) heights[end] = cur->second;
            // 新区间
            if (cur->first <= start && nxt->first > start) {
                max_c = max(max_c, heights[start] = cur->second + 1);
            } else {
                max_c = max(max_c, ++cur->second);
            }
        }
        return max_c;
    }
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(start,end);
 */
// @lc code=end


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/array_and_numbers/sao-miao-xian/meeting-rooms-ii/732.-my-calendar-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.