[差分数组]leetcode732. 我的日程安排表 III(medium)

题目：

---

题解：

思路：差分数组

• 接 729. 我的日程安排表 I 的思路，再还原差分数组时记录最大值即可。

---

代码如下：

class MyCalendarThree {
public:
    MyCalendarThree() {}
    
    map<int,int> b;// 差分数组b
    int book(int l, int r) {
        b[l]+=1,b[r]-=1;
        int res=0,cur=0;
        // 依次还原差分数组ai，ai=b1+b2+...+bi，并记录最大的ai
        for(auto [_,cnt]:b){
            cur+=cnt;
            res=max(res,cur);
        }
        return res;
    }
};