MyCalendar

QUESTION：

MyCalendar.md

My Think：

Today we are talking about MyCalendar I II III. The daily questions for these three days are the same, so we will do them together.

今天我们讲MyCalendar I II III, 这三天的每日一题都是一样的,所以一起做了.

I:

We use binary search to find where startTime can be inserted, and return False if it is found in advance. After finding the insertion point, we can check whether there is overlap.

我们用二分查找, 查找 startTime 在哪里可以插入, 如果提前找到了直接返回 False. 找到了插入点后, 再检查是否有重叠即可.

class MyCalendar:

    def __init__(self):
         self.date = []

    def book(self, startTime: int, endTime: int) -> bool:
        # Binary Search 二分查找 
        n = len(self.date)
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if self.date[mid][0] < startTime:
                left = mid + 1  # Move the left pointer 移动左指针
            elif self.date[mid][0] > startTime:
                right = mid - 1  # Move the right pointer 移动右指针
            else:
                return False  # Find the overlap 发现重叠
        # Check for overlap with previous and next intervals 检查与前后区间的重叠
        if left > 0 and self.date[left - 1][1] > startTime:
            return False
        if left < len(self.date) and self.date[left][0] < endTime:
            return False

        # Insert it 插入区间
        self.date.insert(left, (startTime, endTime))
        return True

II:

This question requires us to check whether there will be three reservations under the conditions of the previous question. Although binary search can also be done, it will be much more complicated. We introduce the idea of ​​differential (Line Sweep) in this question.

1. Record the changes at each time point (start and end)
   When a new interval [startTime, endTime) is to be inserted:

   1. At the position corresponding to startTime +1
   2. At the position corresponding to endTime -1
      In this way, we only record “how much the overlap number should be added/subtracted at these two boundary time points”.

2. Count the current maximum overlap when necessary
   Sort all-time points (keys) from small to large, and accumulate their +1/-1 values in turn.
   The result of the accumulation is the number of activities carried out simultaneously at the corresponding time (that is, the “overlap number”).
   If you want to find out whether there is a triple reservation, see whether the maximum of this accumulation process reaches 3 (or higher)

这道题要求我们在上一道题的条件下, 检查是否会出现三次预定. 二分查找虽然也可以做, 但是会复杂很多. 我们在这一题引入差分(Line Sweep)的思想.

1. 记录每个时间点（开始与结束）的变化
   当有新的区间 [startTime, endTime) 要插入时：

   1. 在 startTime 对应的位置 +1
   2. 在 endTime 对应的位置 -1
      这样我们只记录“在这两个边界时间点，重叠数量要加/减多少”。

2. 在需要时统计当前的最大重叠
   把所有的时间点（key）从小到大排序，依次累加其 +1/-1 值。
   累加的结果就是对应时刻同时进行的活动数量（也就是“重叠数量”）。
   如果要查找是否出现三重预定，就看这个累加过程最大是否到达 3（或更高）

from sortedcontainers import SortedDict
class MyCalendarTwo:
    def __init__(self):
        self.sd = SortedDict()
    def book(self, startTime: int, endTime: int) -> bool:
        self.sd[startTime] = self.sd.get(startTime, 0) + 1
        self.sd[endTime] = self.sd.get(endTime, 0) - 1
        s = 0
        for v in self.sd.values():
            s += v
            if s > 2:
                self.sd[startTime] -= 1
                self.sd[endTime] += 1
                return False
        return True

III:

This question is even more difficult. It requires us to find the maximum number of multiple reservations. We can just record it based on the previous question.

1. Difference record

   Same as before: +1 at the position corresponding to startTime, -1 at the position corresponding to endTime.

   Store in self.sd: key = time point, value = increase or decrease at that time point.

2. Find the maximum number of overlaps

   Use a rolling variable ongoing to indicate “how many overlaps there are at the current moment”.
   Each time a time point is traversed, the corresponding difference is accumulated to ongoing, and then max_overlap = max(max_overlap, ongoing) is updated.

这道题更加过分, 要求我们找到多重预定中最多有多少重, 我们就在上一道题的基础上记录即可.

1. 差分记录

   与之前一致：在 startTime 对应的位置 +1，在 endTime 对应的位置 -1。
   self.sd 中存储：key=时间点, value=该时间点的增减量。

2. 求最大重叠数

   用一个滚动变量 ongoing 表示“当前时刻有多少重叠”。
   每遍历一个时间点，把对应的差分累加到 ongoing，然后更新 max_overlap = max(max_overlap, ongoing)。

from sortedcontainers import SortedDict


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

        self.max_overlap = 0

    def book(self, startTime: int, endTime: int) -> int:
        # First, record the "plus 1" and "minus 1" of this reservation.先把这次预定的“加1”和“减1”记录下来
        self.sd[startTime] = self.sd.get(startTime, 0) + 1
        self.sd[endTime] = self.sd.get(endTime, 0) - 1

        # Temporary variable, record the number of overlaps 临时变量, 记录几折叠
        ongoing = 0 # Current overlap number
        tmp_max = 0
        for v in self.sd.values():
            ongoing += v
            tmp_max = max(ongoing, tmp_max)
        self.max_overlap = max(self.max_overlap, tmp_max)
        return self.max_overlap