732. 我的日程安排表 III

exiaohu 于 2022-06-06 发布

题目链接:732. 我的日程安排表 III

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

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

from sortedcontainers import SortedDict


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

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

        ans, max_book = 0, 0
        for freq in self.events.values():
            ans += freq
            max_book = max(max_book, ans)

        return max_book