[LeetCode]My Calendar III

这道题更general了，每次插入一个区间，我们要返回当前被覆盖最多的层数。首先延续My Calendar II中line sweep的方法仍然是可以做的。空间复杂度O(n)，book的时间复杂度也是O(n)。代码如下：



此外，这也是一道很明显的range query的题目，我们可以用segment tree来解决。具体来说，叶节点存的是当前index对应被覆盖了多少次，非叶节点存的就是这个区间对应的最多的被覆盖的次数。每次插入[s , e]的话就相当于对[s , e]进行range update，区间里的每一个元素加1。区间更新我们用lazy propagation，具体参考上面给出的链接。查询的话直接查根节点储存的信息即可。时间复杂度O(log n)，空间复杂度O(n)，代码如下：