[LeetCode]My Calendar II

这道题和Calendar I的区别是，如果对于book的范围[s, e]中的某一点被三种覆盖了我们才返回false，否则就仍然可以book。我们首先仍然可以延续之前用map维护从小到大不相交的一组interval的方法，区别是这里我们维护的这组interval是已经被二重覆盖的interval，我们称其为list。那么具体的做法是：

1. 对于一个新的interval i，我们首先扫一遍之前所插入过的所有interval，算出i和之前所有插入过的interval的相交的部分的集合，称为overlaps
2. 我们可以明确的一点是，只有这些overlaps中的interval可能造成triple booking。不在overlaps中的部分都没有造成double booking，更不可能和list中的某些interval重叠造成triple booking。
3. 对于overlaps中的interval，我们check list中的intervals看是否会造成triple booking。因为只要和list中的某个interval重叠就会肯定造成triple booking。如果没有的话，我们更新list即可

list的话我们还是想Calendar I一样用BST来存，空间复杂度O(n)，每次book的话时间复杂度也是O(n)，代码如下：

除此之外，我们用line sweep也是可以解决这个问题的。插入新的区间之后，我们从左到右扫一遍然后看某一点是否出现了triple booking即可。每次book的话时间复杂度也是O(n)，代码如下：