LeetCode LCR 058. 我的日程安排表 I

约 5 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
二分查找 LCR 设计 有序集合 线段树

题目描述

✅ LCR 058. 我的日程安排表 I

image-20260929010323221

image-20260929010323222

题意分析

book(start, end) 尝试加入半开区间 [start, end)。与任何已接受日程重叠时返回 false，且不改变日程表；没有重叠则记录区间并返回 true。

右端点不包含在区间内，所以两个日程首尾相接是允许的。已接受区间始终两两不重叠，可以按起点排序，只检查新日程插入位置附近的区间。

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

核心思路

[!blue]

数据结构保持两个性质：已接受区间按起点有序，而且彼此不重叠。对于新区间，只需查看紧邻的前驱和后继，因为其他区间在时间轴上更远。

前驱的起点不晚于 start，只需检查它是否结束得太晚：prev.end > start 表示重叠。后继的起点不早于 start，只需检查新区间是否越过它：end > next.start 表示重叠。等号都允许，因为区间右端不包含在内。

两项检查通过后，前驱及更早区间都结束在 start 之前或恰好结束于它；后继及更晚区间都开始于 end 之后或恰好开始于它。因此其他区间也不可能冲突，可以安全插入。这个结论依赖既有区间不重叠，不能直接用于任意一组相互重叠的区间。

Java 用 TreeMap 保存起点到终点的映射，floorKey(start) 找前驱，ceilingKey(start) 找后继。同起点的已有区间会被检查并拒绝，不会被后面的 put 覆盖。

Go 用有序切片，二分找到第一个起点不小于 start 的位置 l，于是 l 是后继，l-1 是前驱。同起点区间归入后继检查；两边都通过后，扩展切片、把后面的区间右移，再在 l 写入新区间。

两份实现都先检查再写入，失败分支直接返回即可保持旧状态。空日程表、插在最前或最后的位置，只需在访问前驱后继前判断它是否存在。

解题步骤

  1. 按起点有序定位新日程附近的前驱和后继；Go 的二分直接得到插入位置。
  2. 前驱存在且其终点大于 start 时，返回 false。
  3. 后继存在且其起点小于 end 时，返回 false。
  4. 两项检查都通过后记录新区间；Go 先右移后续元素，以维持切片有序。
  5. 返回 true，之后的调用继续以不重叠、有序的已接受区间为基础。

代码实现

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 单次 book 为 $O(\log(m+2))$，执行常数次有序映射查找与插入。Go 二分查询为 $O(\log(m+2))$，成功插入最坏需要移动 $O(m)$ 个区间，因此单次最坏为 $O(m+1)$。
  • 空间复杂度：$O(m)$，保存已接受的日程；被拒绝的预定不进入容器。

关键点总结

[!green]

  • 只检查相邻区间的依据是既有日程有序且两两不重叠。
  • 半开区间允许端点相接，冲突条件使用严格不等号。
  • 检查通过后才插入，让失败预定自然保持原状态。
  • Go 二分只加快定位，不能消除有序切片插入时的搬移成本。

易错点总结

[!yellow]

  • 用大于等于判断端点冲突：会把首尾相接的合法日程拒绝。
  • 只检查前驱或只检查后继：新区间可能向另一个方向延伸并发生重叠。
  • 先写入同起点区间再检查：可能覆盖旧日程；当前实现应在全部检查后写入。
  • 访问不存在的邻居：空表和边界位置可能没有前驱或后继，要先判断。
  • Go 定位后直接追加到末尾：会破坏按起点排序的前提，应在二分得到的位置插入。

相似题目

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