我的日程安排表 II 怎么允许双重预订但禁止三重预订？（LeetCode 731）

简化版

My Calendar II 要允许一个时间点最多被两个预订覆盖，不能出现三重预订。常见做法是维护所有已预订区间 booked 和所有双重重叠区间 overlaps；新预订先检查是否和 overlaps 相交，若相交就会形成三重预订，拒绝；否则把它和 booked 的交集加入 overlaps，再加入 booked。

详细版

区间采用半开形式 [start, end)。两个区间 [a,b) 和 [c,d) 相交，当且仅当 max(a,c) < min(b,d)。My Calendar II 的关键是：三重预订一定来自“新预订与已有双重区间发生交集”。

因此每次 book(start,end) 分三步：先遍历 overlaps，如果新预订和某个双重区间相交，返回 false；再遍历 booked，把新预订与每个已有单区间的交集加入 overlaps；最后把新区间加入 booked 并返回 true。

这个做法单次 O(n)，总计 O(n^2)，但代码直观，适合面试。也可以用 TreeMap 扫描线增减事件，每次试探加入后检查最大覆盖数是否超过 2，失败则回滚。

完整版教学

一、为什么只看双重区间

My Calendar I 是禁止任何重叠；My Calendar II 放宽为允许双重，但禁止三重。也就是说，已有的单重区间可以被新预订重叠一次，但已有的双重区间不能再被新预订碰到。

如果新区间和某个双重区间有交集，那么那一段已经有两场活动，再加上新活动就变成三重预订，必须拒绝。反过来，如果新区间不碰任何双重区间，它和普通预订产生的新交集最多只是双重，可以接受。

记忆钩子：Calendar II 的红线不是“不能重叠”，而是“不能碰已经重叠过的区间”。

二、区间相交公式

半开区间 [a,b) 和 [c,d) 相交的条件是：

max(a, c) < min(b, d)

如果相交，交集就是：

[max(a, c), min(b, d))

注意这里是严格小于。[10,20) 和 [20,30) 的 maxStart=20, minEnd=20，长度为 0，不算相交。

三、两张表法的流程

维护两组区间：

集合	含义	用途
`booked`	所有已接受预订	和新区间求交，产生新的双重区间
`overlaps`	所有已经双重预订的区间	新区间不能与它相交

每次预订先查 overlaps，因为这是硬性拒绝条件。只有确认不会三重后，才把新区间和所有 booked 的交集加入 overlaps。

四、代码模板

class MyCalendarTwo {
    List<int[]> booked = new ArrayList<>();
    List<int[]> overlaps = new ArrayList<>();

    public boolean book(int start, int end) {
        for (int[] o : overlaps) {
            if (Math.max(start, o[0]) < Math.min(end, o[1])) {
                return false;
            }
        }
        for (int[] b : booked) {
            int s = Math.max(start, b[0]);
            int e = Math.min(end, b[1]);
            if (s < e) overlaps.add(new int[]{s, e});
        }
        booked.add(new int[]{start, end});
        return true;
    }
}

顺序不能反。若先把新交集加入 overlaps，再检查 overlaps，就会把新区间和自己刚产生的双重交集误判成三重。

五、数字例子手推

依次预订 [10,20), [50,60), [10,40), [5,15)：

新预订	booked 变化	overlaps 变化	结果
`[10,20)`	加入	无	true
`[50,60)`	加入	无	true
`[10,40)`	加入	`[10,20)`	true
`[5,15)`	不加入	命中 `[10,20)`	false

最后一次 [5,15) 与已有双重区间 [10,20) 相交于 [10,15)，会形成三重预订，所以拒绝。

六、扫描线回滚法

也可以用 TreeMap 记录端点变化：start += 1，end -= 1。每次先试探加入，然后扫描前缀和，如果任意位置超过 2，就回滚这次变化。

events[start] += 1
events[end] -= 1
scan active
if active > 2:
  events[start] -= 1
  events[end] += 1
  return false

扫描线写法更通用，可以扩展到 Calendar III 求最大重叠数。但 Calendar II 面试里，两张表法通常更短、更容易解释。

七、常见误区与追问

误区：只要新区间和 booked 重叠就拒绝。 Calendar II 允许双重预订，普通重叠不一定失败。
误区：忽略半开区间端点相接。 [20,30) 和 [10,20) 不相交。
误区：先更新 overlaps 再检查三重。 会把本次新产生的合法双重区间误当成非法。
追问：为什么碰 overlaps 就一定三重？ overlaps 中每个点已被两个预订覆盖，新区间再覆盖就是三重。
追问：复杂度是多少？ 两张表法单次 O(n)，n 次总 O(n^2)；扫描线每次 O(n) 到 O(n log n) 视实现而定。
追问：Calendar III 怎么做？ 用扫描线累计最大 active，不拒绝预订，只返回历史最大重叠数。

八、加强记忆

My Calendar II 的关键是维护“所有预订”和“已经双重的区间”。新区间可以碰 booked，但不能碰 overlaps；通过 booked 产生的新交集加入 overlaps。相交公式用 max(start) < min(end)，端点相接不算冲突。这个思路比硬套扫描线更容易在面试中讲清楚。

简化版

详细版