729. 我的日程安排表 I

729. 我的日程安排表 I

题目描述

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间区间不会导致 重复预订，则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时，就会产生重复预订。

这里的时间用半开区间表示，即 [start, end)，实数 x 的范围为：

text
start <= x < end

实现 MyCalendar 类：

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

示例

text
输入：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]

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

解释

text
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False ，因为 [15, 25) 和 [10, 20) 重叠
myCalendar.book(20, 30); // return True ，因为 [20, 30) 和 [10, 20) 不重叠

约束

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

核心思路

这题的本质只有一句话：

每次插入新区间时，判断它是否和已有区间重叠。

关键点在于怎么判断两个区间是否重叠。

假设已有区间是 [s1, e1)，新区间是 [s2, e2)。

它们 不重叠 的情况只有两种：

  • 新区间完全在左边：e2 <= s1
  • 新区间完全在右边：s2 >= e1

那么它们 重叠 的条件就是上面两种情况的反面：

ts
start < existedEnd && end > existedStart

也可以记成：

ts
Math.max(start, existedStart) < Math.min(end, existedEnd)

这题至少有两种常见做法：

  • 解法一：顺序扫描所有已预订区间
  • 解法二：按开始时间有序存储 + 二分查找插入位置

解法一：顺序扫描所有区间

这是最直接、最适合第一次做这题的做法。

思路拆解

我们用一个数组 books 存所有已经成功预订的区间。

每次调用 book(start, end)：

  1. 遍历 books 中每一个旧区间
  2. 判断新区间和旧区间是否重叠
  3. 如果重叠，直接返回 false
  4. 如果全部都不重叠，就把新区间加入数组并返回 true

由于最多调用 1000 次，O(n) 扫描完全够用。

一步一步写出算法

第一步：先定义数据结构

我们需要一个数组来保存所有已经预订成功的区间。

ts
class MyCalendar {
    private books: [number, number][]

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

第二步：思考怎么判断是否重叠

对于旧区间 [left, right)，如果满足：

ts
start < right && end > left

说明有交集，也就是重叠。

为什么这样判断？

  • start < right 说明新区间左端点在旧区间右端点左边
  • end > left 说明新区间右端点在旧区间左端点右边
  • 两者同时成立，说明它们真正压在了一起

第三步：遍历所有旧区间

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

第四步：如果没有重叠，就加入数组

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

代码实现（TypeScript）

ts
class MyCalendar {
    private books: [number, number][]

    constructor() {
        this.books = []
    }

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

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

复杂度分析

  • 单次 book 时间复杂度：O(n)
  • 总时间复杂度：O(n^2)
  • 空间复杂度：O(n)

这里的 n 是成功预订的区间数量。

这一解法的优缺点

优点：

  • 最容易理解
  • 最容易写对
  • 对这题的数据范围已经足够

缺点：

  • 每次都要扫一遍已有区间
  • 当预订次数更多时，不够高效

解法二：按开始时间有序存储 + 二分查找

这个做法的重点是：

如果区间按开始时间有序，那么新区间只需要检查“插入位置附近”的区间即可。

为什么只检查相邻区间？

假设我们已经把所有区间按 start 从小到大排序。

现在要插入新区间 [start, end)，并且它最终应该放在下标 idx 的位置。

那么：

  • 它左边最可能和它冲突的是 idx - 1
  • 它右边最可能和它冲突的是 idx

因为更左边的区间结束得更早，更右边的区间开始得更晚。

所以我们不用扫描全部区间，只要检查左右邻居即可。

一步一步写出算法

第一步：仍然先定义数组

只是这次要求数组始终按开始时间有序。

ts
class MyCalendar {
    private books: [number, number][]

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

第二步：二分查找插入位置

我们要找到第一个 books[mid][0] >= start 的位置。

ts
let left = 0
let right = this.books.length

while (left < right) {
    const mid = Math.floor((left + right) / 2)
    if (this.books[mid][0] < start) {
        left = mid + 1
    } else {
        right = mid
    }
}

循环结束后，left 就是新区间应该插入的位置。

第三步：检查左边邻居

如果 left - 1 存在，那么它是新区间左边最近的区间。

只要它的结束时间大于新区间开始时间，就冲突。

ts
if (left > 0 && this.books[left - 1][1] > start) {
    return false
}

第四步：检查右边邻居

如果 left 还在数组范围内，那么它就是新区间右边最近的区间。

只要新区间结束时间大于右边邻居的开始时间，就冲突。

ts
if (left < this.books.length && end > this.books[left][0]) {
    return false
}

第五步：在正确位置插入新区间

ts
this.books.splice(left, 0, [start, end])
return true

代码实现（TypeScript）

ts
class MyCalendar {
    private books: [number, number][]

    constructor() {
        this.books = []
    }

    book(start: number, end: number): boolean {
        let left = 0
        let right = this.books.length

        while (left < right) {
            const mid = Math.floor((left + right) / 2)
            if (this.books[mid][0] < start) {
                left = mid + 1
            } else {
                right = mid
            }
        }

        if (left > 0 && this.books[left - 1][1] > start) {
            return false
        }

        if (left < this.books.length && end > this.books[left][0]) {
            return false
        }

        this.books.splice(left, 0, [start, end])
        return true
    }
}

复杂度分析

  • 二分查找：O(log n)
  • 数组插入：O(n)
  • 单次 book 总时间复杂度：O(n)
  • 空间复杂度：O(n)

虽然插入仍然是 O(n)，但相比暴力扫描，它的“查找冲突区间”更有思路，也更接近更高级数据结构的做法。

两种解法对比

解法查找方式单次时间复杂度空间复杂度特点
顺序扫描遍历全部区间O(n)O(n)最直观，最适合入门
有序数组 + 二分二分定位 + 邻居检查O(n)O(n)思路更进阶，更接近面试优化

注意：

  • 第二种方法虽然用了二分，但由于数组插入需要移动元素，所以单次仍是 O(n)。
  • 如果底层是平衡树，那么查找和插入都可以更高效，但在 LeetCode 的 TypeScript 环境里通常不会这么写。

手动模拟一遍

以题目示例为例：

text
book(10, 20) -> true
book(15, 25) -> false
book(20, 30) -> true

第一次：book(10, 20)

当前还没有任何区间。

text
[]

直接插入：

text
[10, 20)

返回 true。

第二次：book(15, 25)

检查和 [10, 20) 是否重叠：

text
15 < 20 并且 25 > 10

说明重叠，所以返回 false。

日历不变：

text
[10, 20)

第三次：book(20, 30)

检查和 [10, 20) 是否重叠：

text
20 < 20 ? 不成立

因为这是半开区间，[10, 20) 和 [20, 30) 只是刚好相接，不算重叠。

所以可以插入，返回 true。

最终日历：

text
[10, 20), [20, 30)

面试时最容易错的点

1. 别把“相接”当成“重叠”

这题是半开区间：

text
[10, 20) 和 [20, 30)

它们 不重叠。

所以判断时要用：

ts
start < right && end > left

而不是写成 <= 或 >=。

2. 重叠条件建议直接背下来

两个区间 [a, b) 和 [c, d) 重叠，当且仅当：

ts
a < d && b > c

在本题中就是：

ts
start < right && end > left

3. 二分法里只检查相邻区间

很多人会觉得二分找到位置后，还要继续往两边扫。

其实不用。

因为区间已经按开始时间排序，真正可能冲突的只会是插入位置左右两侧的邻居。

一句话总结

这题本质上是：

维护一组互不重叠的区间，每次插入新区间时判断它是否和已有区间冲突。

  • 想先写对：用 顺序扫描
  • 想把思路再进一层：用 有序数组 + 二分查找

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

如果你准备用 TypeScript 刷题，最推荐记住下面这个版本：

ts
class MyCalendar {
    private books: [number, number][]

    constructor() {
        this.books = []
    }

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

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

原因很简单：

  • 最稳
  • 最不容易写错
  • 对这题的数据范围完全够用