732. My Calendar III

https://leetcode.com/problems/my-calendar-iii/description/

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

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

/*
 * @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