[LeetCode] 每日一题 729. 我的日程安排表 I

题目链接

题目描述

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

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。

日程可以用一对整数 startTime 和 endTime 表示，这里的时间是半开区间，即 [startTime, endTime), 实数 x 的范围为，  startTime <= x < endTime 。

实现 MyCalendar 类：

• MyCalendar() 初始化日历对象。

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

示例输入

示例

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

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

解释：
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False ，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。
myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20 ，且不包含时间 20 。

提示

• 0 <= start < end <= 109

• 每个测试用例，调用 book 方法的次数最多不超过 1000 次。

题解

思路

我们需要实现一个数据结构来存储已预定的时间段，同时保证新预定的时间段不会与已有的时间段重叠

使用 TreeSet

• 数据结构选择： TreeSet 是一个有序集合，支持按自然顺序或自定义顺序排序。通过 TreeSet，我们可以快速找到与给定区间相邻的时间段

• 关键操作：

  1. ceiling 方法： 找到大于等于某个值的最小区间

  2. lower 方法： 找到严格小于某个值的最大区间

• 解决思路：

  1. 初始化一个 TreeSet，用来存储已预定的时间段

  2. 对于每次预定的时间段 start, end：

     • 使用 ceiling 找到第一个开始时间大于等于 end 的区间

     • 使用 lower 找到前一个区间

  3. 检查与前后区间是否有重叠：

     • 前一个区间的结束时间必须小于等于 start

     • 后一个区间的开始时间必须大于等于 end

  4. 如果没有冲突，则将当前区间加入到 TreeSet

代码实现

class MyCalendar {
    // 使用 TreeSet 存储已预定的时间段，按起始时间排序
    TreeSet<int[]> bookings;

    public MyCalendar() {
        // 初始化 TreeSet，按起始时间排序
        bookings = new TreeSet<>((a, b) -> Integer.compare(a[0], b[0]));
    }

    public boolean book(int start, int end) {
        // 如果当前没有任何预订，直接添加并返回成功
        if (bookings.isEmpty()) {
            bookings.add(new int[] { start, end });
            return true;
        }

        // 找到第一个开始时间大于等于新事件结束时间的区间
        int[] nextEvent = bookings.ceiling(new int[] { end, 0 });

        // 找到新事件之前的区间
        int[] previousEvent = nextEvent == null ? bookings.last() : bookings.lower(nextEvent);

        // 检查是否与前一个或后一个事件有冲突
        if ((previousEvent == null || previousEvent[1] <= start) &&
                (nextEvent == null || nextEvent[0] >= end)) {
            bookings.add(new int[] { start, end });
            return true;
        }

        // 存在冲突，预订失败
        return false;
    }
}

复杂度分析

时间复杂度

• book 方法：

  1. 查找前后区间的复杂度为 O(log n)，因为 TreeSet 的操作基于平衡二叉树

  2. 添加区间的复杂度为 O(log n)

  3. 总体复杂度为 O(log n)

空间复杂度

• 每次成功预定会存储一个区间，空间复杂度为 O(n)，其中 n 是成功预定的次数

总结

• 本题使用 TreeSet 来高效地管理区间数据，避免重复预定

• TreeSet 提供的 ceiling 和 lower 方法大大简化了逻辑，使得我们可以在 O(log n) 时间内完成预定操作

• 该解决方案适用于需要处理区间冲突的其他类似场景，如会议室预定等

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。