[LeetCode]My Calendar I

假设当前插入的interval为[start, end)，那么我们要做的是查找之前插入的interval有没有overlap的部分。做法很多，可以维护一个按照start从小到大sorted的list，list当中每个interval都不相交。每次插入interval i1的时候二分法查找小于end的最大start值对应的interval i2，看i2是否和i1相交即可。维护sorted的list的代价太大，我们每一次插入都需要保证list仍然是sorted的，那么我们可以改用BST来存，key为start，value为end即可，思路是一样的。时间复杂度O(log n)，n为intervals的总数。代码如下：