731. 我的日程安排表 II

731. 我的日程安排表 II

题目描述

实现一个 MyCalendarTwo 类来存放你的日程安排。你可以一直添加新的日程安排，但要求 不能出现三重预订。

所谓三重预订，指的是同一个时间点上同时有 三个 日程安排。

这题依然使用半开区间 [start, end)，也就是：

text
start <= x < end

实现 MyCalendarTwo 类：

  • MyCalendarTwo() 初始化日历对象。
  • boolean book(int start, int end) 如果该日程安排可以成功添加到日历中而不会导致三重预订，返回 true；否则返回 false，并且不能添加该日程安排。

示例

text
输入：
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

输出：
[null, true, true, true, false, true, true]

解释

text
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // true
myCalendarTwo.book(50, 60); // true
myCalendarTwo.book(10, 40); // true
myCalendarTwo.book(5, 15);  // false
myCalendarTwo.book(5, 10);  // true
myCalendarTwo.book(25, 55); // true

约束

  • 0 <= start < end <= 10^9
  • 调用 book 的次数最多为 1000

核心思路

729 题要求 不能重复预订，也就是连“两重预订”都不允许。

而这题放宽成：

  • 允许双重预订
  • 不允许三重预订

所以这题的关键是：

新增一个区间时，只要它和某段“已经双重预订的区间”再次重叠，就会产生三重预订。

因此我们可以从两个角度来做：

  • 解法一：维护单预订区间 + 双预订区间
  • 解法二：扫描线 / 差分统计每个时间点的覆盖次数

解法一：维护 books 和 overlaps

这是这题最经典、最适合面试表达的做法。

思路拆解

我们维护两个数组：

  • books：所有成功预订的一次区间
  • overlaps：所有已经出现过的“双重预订区间”

当我们尝试加入新区间 [start, end) 时：

  1. 先检查它是否和某个 overlaps 重叠
  2. 如果重叠，说明会把“双重预订”再压成“三重预订”，直接返回 false
  3. 如果不会和任何 overlaps 重叠，再去遍历所有 books
  4. 新区间如果和某个旧区间重叠，那么这段交集会变成新的“双重预订区间”，加入 overlaps
  5. 最后把新区间本身加入 books

为什么这样做是对的？

因为：

  • books 记录的是“至少被订了 1 次”的区间
  • overlaps 记录的是“已经被订了 2 次”的区间

那么新区间一旦和 overlaps 中的任何区间再相交，那个相交部分就会被订到第 3 次，违反题意。

所以：

先查 overlaps，再更新新的 overlaps，最后加入 books。

顺序不能乱。

一步一步写出算法

第一步：先定义两个数组

ts
class MyCalendarTwo {
    private books: [number, number][]
    private overlaps: [number, number][]

    constructor() {
        this.books = []
        this.overlaps = []
    }
}

第二步：先判断会不会产生三重预订

只要新区间和任意一个双重预订区间重叠，就必须拒绝。

区间重叠条件依然是：

ts
start < right && end > left

代码：

ts
for (const [left, right] of this.overlaps) {
    if (start < right && end > left) {
        return false
    }
}

第三步：计算它和旧区间的交集

如果新区间和某个已预订区间有重叠，那么这段交集会成为新的双重预订区间。

交集写法：

ts
const overlapStart = Math.max(start, left)
const overlapEnd = Math.min(end, right)

只要满足 overlapStart < overlapEnd，就说明交集有效。

ts
for (const [left, right] of this.books) {
    const overlapStart = Math.max(start, left)
    const overlapEnd = Math.min(end, right)
    if (overlapStart < overlapEnd) {
        this.overlaps.push([overlapStart, overlapEnd])
    }
}

第四步：把新区间加入 books

ts
this.books.push([start, end])
return true

代码实现（TypeScript）

ts
class MyCalendarTwo {
    private books: [number, number][]
    private overlaps: [number, number][]

    constructor() {
        this.books = []
        this.overlaps = []
    }

    book(start: number, end: number): boolean {
        for (const [left, right] of this.overlaps) {
            if (start < right && end > left) {
                return false
            }
        }

        for (const [left, right] of this.books) {
            const overlapStart = Math.max(start, left)
            const overlapEnd = Math.min(end, right)
            if (overlapStart < overlapEnd) {
                this.overlaps.push([overlapStart, overlapEnd])
            }
        }

        this.books.push([start, end])
        return true
    }
}

复杂度分析

  • 单次 book 时间复杂度：最坏可到 O(n^2)
  • 更准确地说：需要遍历 books 和 overlaps
  • 在本题数据范围下可以通过
  • 空间复杂度：O(n^2)

为什么空间可能到 O(n^2)？

因为不同区间两两相交时，会产生很多双重预订区间。

这一解法的优缺点

优点：

  • 思路很清楚
  • 很适合讲“为什么不会出现三重预订”
  • 面试里非常常见

缺点：

  • overlaps 可能越来越多
  • 不是最简洁的“统一计数”写法

解法二：扫描线 / 差分

这个做法更像是在维护“每个时间点被覆盖了几次”。

思路拆解

对于一个区间 [start, end)：

  • 在 start 位置做 +1
  • 在 end 位置做 -1

然后把所有时间点按顺序扫一遍，累加当前活跃区间数量：

  • 如果任何时刻累计值超过 2
  • 就说明出现了三重预订
  • 这次插入必须撤销

所以：

  1. 先把这次预订临时加到差分表里
  2. 按时间排序扫描前缀和
  3. 如果发现某处前缀和 > 2，就撤销本次修改并返回 false
  4. 否则返回 true

一步一步写出算法

第一步：定义差分表

我们可以用 Map<number, number> 来表示：

  • 某个时间点的增量是多少
ts
class MyCalendarTwo {
    private diff: Map<number, number>

    constructor() {
        this.diff = new Map()
    }
}

第二步：先尝试加入新区间的影响

ts
this.diff.set(start, (this.diff.get(start) ?? 0) + 1)
this.diff.set(end, (this.diff.get(end) ?? 0) - 1)

第三步：按时间从小到大扫描

ts
const times = Array.from(this.diff.keys()).sort((a, b) => a - b)
let active = 0

for (const time of times) {
    active += this.diff.get(time)!
    if (active > 2) {
        // 撤销
    }
}

第四步：如果超过 2，就撤销修改

因为刚才是“先试着加进去”，所以一旦失败，要恢复现场。

ts
this.diff.set(start, this.diff.get(start)! - 1)
if (this.diff.get(start) === 0) {
    this.diff.delete(start)
}

this.diff.set(end, this.diff.get(end)! + 1)
if (this.diff.get(end) === 0) {
    this.diff.delete(end)
}

return false

第五步：如果扫描结束都没超过 2，就说明可以预订

ts
return true

代码实现（TypeScript）

ts
class MyCalendarTwo {
    private diff: Map<number, number>

    constructor() {
        this.diff = new Map()
    }

    book(start: number, end: number): boolean {
        this.diff.set(start, (this.diff.get(start) ?? 0) + 1)
        this.diff.set(end, (this.diff.get(end) ?? 0) - 1)

        const times = Array.from(this.diff.keys()).sort((a, b) => a - b)
        let active = 0

        for (const time of times) {
            active += this.diff.get(time)!
            if (active > 2) {
                this.diff.set(start, this.diff.get(start)! - 1)
                if (this.diff.get(start) === 0) {
                    this.diff.delete(start)
                }

                this.diff.set(end, this.diff.get(end)! + 1)
                if (this.diff.get(end) === 0) {
                    this.diff.delete(end)
                }

                return false
            }
        }

        return true
    }
}

复杂度分析

  • 每次 book 需要对所有时间点排序并扫描
  • 如果当前有 m 个不同时间点：
    • 排序复杂度：O(m log m)
    • 扫描复杂度：O(m)
  • 总体可写成：O(m log m)
  • 空间复杂度：O(m)

在本题最多 1000 次调用下，这个做法同样可以通过。

两种解法对比

解法核心维护对象单次时间复杂度空间复杂度特点
books + overlaps单预订区间、双预订区间O(n) 到 O(n^2)O(n^2)面试最常见，思路很好讲
差分 / 扫描线每个时间点的覆盖增量O(m log m)O(m)更统一，适合理解区间计数

如果你是第一次做 731，更推荐先完全掌握第一种方法。

因为它直接抓住了本题的本质：

只要新区间碰到“双重预订区间”，就会变成三重预订。

手动模拟一遍经典解法

我们用题目里的例子：

text
book(10, 20) -> true
book(50, 60) -> true
book(10, 40) -> true
book(5, 15)  -> false

第一次：book(10, 20)

  • books = []
  • overlaps = []

没有任何冲突，直接加入：

text
books = [[10, 20)]
overlaps = []

第二次：book(50, 60)

和已有区间不重叠，直接加入：

text
books = [[10, 20), [50, 60)]
overlaps = []

第三次：book(10, 40)

先检查 overlaps，目前为空，所以不会产生三重预订。

然后和 books 中区间比较：

  • 和 [10, 20) 的交集是 [10, 20)
  • 和 [50, 60) 没交集

所以新增一个双重预订区间：

text
overlaps = [[10, 20)]

最后把 [10, 40) 加入 books：

text
books = [[10, 20), [50, 60), [10, 40)]

第四次：book(5, 15)

先检查它和 overlaps = [[10, 20)] 是否重叠。

确实重叠，因为：

text
5 < 20 且 15 > 10

这意味着 [10, 15) 这一段会同时出现在三个区间里：

  • [10, 20)
  • [10, 40)
  • [5, 15)

因此产生三重预订，必须返回 false。

面试时最容易错的点

1. 一定要先检查 overlaps

这是第一种解法里最关键的顺序。

如果先把新区间和 books 更新出新的 overlaps，再去检查，逻辑会容易绕乱，甚至误判。

正确顺序是：

  • 先看会不会撞上已有双重预订区间
  • 再生成新的双重预订区间
  • 最后加入新区间

2. 半开区间边界别写错

[10, 20) 和 [20, 30) 不重叠。

所以重叠条件仍然是：

ts
start < right && end > left

不要写成 <= 或 >=。

3. 差分法失败后要撤销

扫描线做法里，很多人会忘记：

  • 你是先把这次预订“试着加进去”
  • 如果发现超过 2
  • 一定要把 start 和 end 的改动撤销回来

否则后续状态就错了。

一句话总结

这题的本质是：

允许重复一次，但不能重复到第三次。

所以最经典的做法就是：

  • 用 books 记录所有已预订区间
  • 用 overlaps 记录所有双重预订区间
  • 新区间只要碰到 overlaps，就直接拒绝

推荐你最后记住的标准写法

如果你准备面试，建议优先记下面这个版本：

ts
class MyCalendarTwo {
    private books: [number, number][]
    private overlaps: [number, number][]

    constructor() {
        this.books = []
        this.overlaps = []
    }

    book(start: number, end: number): boolean {
        for (const [left, right] of this.overlaps) {
            if (start < right && end > left) {
                return false
            }
        }

        for (const [left, right] of this.books) {
            const overlapStart = Math.max(start, left)
            const overlapEnd = Math.min(end, right)
            if (overlapStart < overlapEnd) {
                this.overlaps.push([overlapStart, overlapEnd])
            }
        }

        this.books.push([start, end])
        return true
    }
}

因为这个版本：

  • 最贴合题目本质
  • 最适合解释“为什么不会三重预订”
  • 在 1000 次调用的数据范围下完全够用