LeetCode 729. 我的日程安排表 I

约 4 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 二分查找 设计 有序集合 线段树

题目描述

✅ 729. 我的日程安排表 I

image-20260929104631507

image-20260929104631676

题意分析

依次预订半开区间 [start, end)，若与任何已接受的预订重叠就返回 false，并且不保存这次预订；否则保存并返回 true。结束时刻不属于区间，因此两个区间仅在首尾相接时不算重叠。

解法：TreeMap / 有序映射维护区间

核心思路

[!blue]

所有已接受的区间互不重叠，按开始时间有序保存。新区间可能冲突的边界只有两侧邻居：左侧最近区间的结束时间若大于 start，它与新区间重叠；右侧最近区间的开始时间若小于 end，新区间就延伸进了它。

只检查邻居已经足够。更早的区间与左邻居不重叠，所以结束得更早；更晚区间的起点也不会早于右邻居。两侧邻居都不冲突时，其余区间同样不会冲突。边界相等只表示首尾相接，所以冲突判断使用严格大于，而不是大于等于。

Java 用 floorKey(start) 找起点不大于 start 的最近区间，用 ceilingKey(start) 找起点不小于它的最近区间。同起点的旧区间也会被找到，由于区间长度为正，必然被拒绝，不会覆盖原记录。

Go 对有序切片二分，找到第一个起点不小于 start 的下标 l，检查 l-1 与 l 两个位置。通过后先扩展一个空位，将后缀整体右移，再写入新区间。两种实现都先完成检查再修改存储，拒绝的预订不会影响后续调用。

解题步骤

  1. 按起点找到当前区间的插入位置。
  2. 若前驱结束时间大于 start，拒绝。
  3. 若后继开始时间小于 end，拒绝。
  4. 通过检查后写入结构，保留半开区间的相邻不重叠语义。

代码实现

class MyCalendar {
    private final TreeMap<Integer, Integer> map = new TreeMap<>();

    public boolean book(int start, int end) {
        Integer prevStart = map.floorKey(start);

        // 前驱结束不得超过当前开始，相等只是边界相接。
        if (prevStart != null && map.get(prevStart) > start) {
            return false;
        }

        Integer nextStart = map.ceilingKey(start);

        // 当前结束不得越过后继开始，通过两侧检查后才插入。
        if (nextStart != null && end > nextStart) {
            return false;
        }

        map.put(start, end);

        return true;
    }
}

type MyCalendar struct {
    intervals [][2]int
}

func Constructor() MyCalendar {
    return MyCalendar{intervals: make([][2]int, 0)}
}

func (c *MyCalendar) Book(start int, end int) bool {
    l, r := 0, len(c.intervals)
    for l < r {
        mid := (l + r) / 2
        if c.intervals[mid][0] < start {
            l = mid + 1
        } else {
            r = mid
        }
    }

    // 前驱结束不得超过当前开始，相等只是边界相接。
    if l > 0 && c.intervals[l-1][1] > start {
        return false
    }
    // 当前结束不得越过后继开始，通过两侧检查后才插入。
    if l < len(c.intervals) && end > c.intervals[l][0] {
        return false
    }

    c.intervals = append(c.intervals, [2]int{})
    copy(c.intervals[l+1:], c.intervals[l:])
    c.intervals[l] = [2]int{
        start,
        end,
    }
    return true
}

复杂度分析

  • 时间复杂度：已有 m 个预订时，Java 单次 $O(\log(m+1))$；Go 二分 $O(\log(m+1))$，切片插入移动元素最坏 $O(m)$。
  • 空间复杂度：保存 m 个区间需要 $O(m)$。

关键点总结

[!green]

  • 半开区间允许 end 与下一段 start 相等。
  • 邻居检查依赖已有区间互不重叠这一不变量。
  • 先检查再写入，失败预订不会污染后续状态。

易错点总结

[!yellow]

  • 用大于等于判断前驱冲突：会拒绝合法的边界相接。
  • 只检查前驱：新区间可能越过后继的开始时间。
  • 失败后仍保留新区间：后续查询会受到非法预订影响。
  • 将 Go 有序切片的单次操作写成对数时间：二分之外还有插入移动。

相似题目

题目 难度 关联与区别
731. 我的日程安排表 II 中等 本题禁止任何重叠，原题允许双重预订但禁止三重预订，需要追踪更高层重叠。
732. 我的日程安排表 III 困难 同样处理半开时间区间，原题直接维护最大同时预订数，而不是接受或拒绝新日程。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/17038017
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！