731. 我的日程安排表 II

exiaohu 于 2022-07-19 发布

题目链接:731. 我的日程安排表 II

用一个差分数组记录日程数量,当一个日程开始时,计数加一,结束时计数减一。

然后遍历一遍这个差分数组,就可以得到重叠最多的预订日程数量。

这个数量大于 $2$ 时,无法预订。

from sortedcontainers import SortedDict


class MyCalendarTwo:
    def __init__(self):
        self.events = SortedDict()

    def book(self, start: int, end: int) -> bool:
        self.events[start] = self.events.setdefault(start, 0) + 1
        self.events[end] = self.events.setdefault(end, 0) - 1

        max_book = 0
        for freq in self.events.values():
            max_book += freq
            if max_book > 2:
                self.events[start] = self.events.get(start, 0) - 1
                self.events[end] = self.events.get(end, 0) + 1
                return False

        return True