我的日程安排表 III

难度: Hard

当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。

给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

MyCalendarThree() 初始化对象。
int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

示例：

输入：
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, 1, 1, 2, 3, 3, 3]

解释：
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

提示：

0 <= start < end <= 10⁹
每个测试用例，调用 book 函数最多不超过 400次

Submission

运行时间: 93 ms

内存: 16.5 MB

from bisect import bisect_left

class MyCalendarThree:
    def __init__(self):
        self.s, self.e = [], []
        self.cap = 1
    def book(self, start: int, end: int) -> int:
        ind1, ind2 = bisect_right(self.e, start), bisect_left(self.s, end)
        
        p1 = ind1
        curr = 1
        for st in range(ind1, ind2):
            
            if self.s[st]<self.e[p1]: curr += 1
            else: p1 += 1
            self.cap = max(self.cap, curr)
        bisect.insort(self.s, start)
        bisect.insort(self.e, end)
        return self.cap
    '''def __init__(self):
        self.hmax, self.hs, self.marks=0, [], []

    def book(self, start: int, end: int) -> int:

        i=bisect_left(self.marks, start)
        if i==len(self.marks) or self.marks[i]!=start:
            self.marks=self.marks[:i]+[start]+self.marks[i:]
            self.hs=self.hs[:i]+[self.hs[i-1] if i>0 else 0]+self.hs[i:]
            
        j=bisect_left(self.marks, end)
        if j==len(self.marks) or self.marks[j]!=end:
            self.marks=self.marks[:j]+[end]+self.marks[j:]
            self.hs=self.hs[:j]+[self.hs[j-1]]+self.hs[j:]
    
        for k in range(i,j):
            self.hs[k]+=1
        hmax=max(self.hs[i:j])
        self.hmax=max(hmax,self.hmax)
        return self.hmax'''

Explain

这个题解使用了差分数组的思路。具体来说，它维护了两个有序数组 s 和 e，分别存储所有日程的开始时间和结束时间。当插入一个新的日程 [start, end) 时，它先通过二分查找找到 start 在 e 中的插入位置 ind1，以及 end 在 s 中的插入位置 ind2。然后从 ind1 开始遍历，用一个变量 curr 记录当前的预订次数，如果遇到一个日程的开始时间小于当前指针 p1 指向的日程的结束时间，说明发生了交叉，curr 就加 1。每次更新 curr 后都要更新答案 cap。最后再将 start 插入 s，将 end 插入 e。

时间复杂度: O(n)

空间复杂度: O(n)

from bisect import bisect_left, bisect_right

class MyCalendarThree:
    def __init__(self):
        self.s, self.e = [], []
        self.cap = 1

    def book(self, start: int, end: int) -> int:
        # 找到 start 在 e 中的插入位置
        ind1 = bisect_right(self.e, start)
        # 找到 end 在 s 中的插入位置
        ind2 = bisect_left(self.s, end)
        
        p1 = ind1
        curr = 1
        for st in range(ind1, ind2):
            # 如果当前日程的开始时间小于指针 p1 指向的日程的结束时间，说明发生了交叉
            if self.s[st] < self.e[p1]:
                curr += 1
            else:
                p1 += 1
            # 更新答案
            self.cap = max(self.cap, curr)
        # 将 start 插入 s
        bisect.insort(self.s, start)
        # 将 end 插入 e
        bisect.insort(self.e, end)
        return self.cap

Explore

数组s和e保持有序是通过使用Python的标准库函数`bisect.insort`实现的，该函数可以在保持列表有序的情况下插入新元素。确实，插入操作会影响性能，因为在有序数组中插入一个元素的时间复杂度通常是O(n)，其中n是数组的长度。这意味着每次插入都需要在找到插入点后，移动插入点后的所有元素以保持数组的有序性。这在频繁插入且数据量较大时会相对耗时。

ind1是使用`bisect_right`计算的，这意味着它会找到第一个大于start的结束时间的位置，在这之前的所有结束时间都不可能与新的开始时间start重叠。ind2是使用`bisect_left`计算的，这意味着它会找到第一个不小于end的开始时间的位置。这种方式确保了所有可能与新日程[start, end)重叠的区间都会在start和end之间被检查到，从而不会错过任何重叠区间。

p1指针在遍历过程中的更新逻辑是如果当前日程的开始时间小于p1指向的日程的结束时间，则认为发生了交叉，否则p1递增。这种逻辑确保了只要存在交叉，p1就不会递增，因此不会遗漏任何交叉的日程。然而，此逻辑依赖于数组s和e的正确和有序，任何错误或处理不当都可能导致遗漏或错误计算。

使用`bisect_right`和`bisect_left`确保了在有序数组中正确地找到插入位置。`bisect_right`返回的是插入点右侧的位置，适用于找到所有小于等于给定值的元素的场景；而`bisect_left`返回的是插入点左侧的位置，适用于找到所有小于给定值的元素的场景。这两个函数的选择关键影响了算法的正确性，确保了不会错过检查任何可能的重叠日程。在效率方面，这两个函数的执行时间复杂度为O(log n)，使得查找插入位置比较高效，但实际插入操作仍然是O(n)。