当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。
给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。
给出一种比较慢的做法，就是遍历所有的区间，取最大的值。
由于本题是整数，且0 <= start < end <= 109，所以可以记录0-109的所有数的个数最大值，就像柏青哥一样。
截屏2022-06-06 下午10.41.24.png
class MyCalendarThree:
# 在x轴上面扔火柴棒，看最高的火柴棒个数
# 跟之前的一道题很像
def __init__(self):
self.order = dict()
def book(self, start: int, end: int) -> int:
def check(k1, k2):
# 计算交集
if k1[0]>=k2[1] or k1[1]<=k2[0]:
return []
else:
if k2[0] <= k1[0] <= k2[1]:
return [k1[0], min(k1[1],k2[1])]
elif k1[0] <= k2[0] <= k1[1]:
return [k2[0], min(k1[1],k2[1])]
# 遍历order
spans = list(self.order.keys())
for span in spans:
s1, e1 = [int(v) for v in span.split(',')]
intersection = check([start, end], [s1, e1])
if len(intersection) > 0:
intersection_key = f'{intersection[0]},{intersection[1]}'
if intersection_key in self.order:
self.order[intersection_key] = max(self.order[intersection_key], self.order[span] + 1)
else:
self.order[intersection_key] = self.order[span] + 1
key = f'{start},{end}'
if not key in self.order:
self.order[key] = 1
# print(self.order)
return max(self.order.values())
# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(start,end)
