Leetcode地址：729. 我的日程安排表 I - 力扣（LeetCode）

题目理解：

两个区间[s1,e1],[s2,e2]无交集的时候，e1<=s2或，e2<=s1。故而判定有交集的时候：s1<e2 and e1>s2

解法1.直接遍历

时间复杂度：O（n^2)

空间复杂度：O（n)

代码如下:

class MyCalendar:def __init__(self):self.books=[]def book(self, start: int, end: int) -> bool:if any(start<r and end>l for l,r in self.books):return Falseself.books.append((start,end))return True

解法2:二分查找

根据性质，start插入的位置应为偶数，且end小于后一个位置，因为后一个位置是下一个区间的开始。

时间复杂度：O（nlogn), 二分查找的时间复杂度为O（logn)

空间复杂度：O（n）

因为这里如果出现(10,20)(20,30)这种start2=end1的情况，是属于不交叉的，所以二分查找时选择bisect_right

!需要注意的是，book[i:i]的赋值在python中是O(n)的复杂度，数据量大时会超时。

代码如下：

from bisect import bisect_right
class MyCalendar:def __init__(self):self.books=[]def book(self, start: int, end: int) -> bool:i=bisect_right(self.books,start)if i%2==1 or (i<len(self.books) and self.books[i]<end):return Falseself.books[i:i]=[start,end]return True