我的日程安排表II

2025-01-03

题目：

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

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

事件能够用一对整数 startTime 和 endTime 表示，在一个半开区间的时间 [startTime, endTime) 上预定。实数 x 的范围为 startTime <= x < endTime。

实现 MyCalendarTwo 类：

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

示例 1：

输入：
["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]

解释：
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，能够预定该日程，因为它不使用已经双重预订的时间 10。
myCalendarTwo.book(25, 55); // 返回 True，能够预定该日程，因为时间段 [25, 40) 将被第三个日程重复预定，时间段 [40, 50) 将被单独预定，而时间段 [50, 55) 将被第二个日程重复预定。

提示：

  • 0 <= start < end <= 109
  • 最多调用 book 1000 次。

思路：

记录下所有已经预定的课程安排区间与已经预定过两次的课程安排区间，当我们预定新的区间 [start,end) 时，此时检查当前已经预定过两次的每个日程安排是否与新日程安排冲突。若不冲突，则可以添加新的日程安排。

对于两个区间 [s1，e1) 和 [s2，e2)，如果二者没有交集，则此时应当满足 s1 ≥ e2 或者 s2 ≥ e1，这就意味着如果满足 s1 < e2 并且 s2 < e1 时，则两者会产生差集。
首先检测新加入的区间 [start,end) 是否与已经预定过两次的区间有交集，如果没有冲突，则将新加入的区间与已经预定的区间进行检查，求出新增的预定两次的区间。对于两个区间 [s1，e1) 和 [s2，e2)，则他们之间的交集为 [max(s1, s2), min(e1, e2))。

代码：

class MyCalendarTwo {
private:
    vector<pair<int, int>> booked; // 被预定过一次的区间
    vector<pair<int, int>> overlaps; // 被预定过两次的区间
public:
    MyCalendarTwo() {
        
    }
    
    bool book(int startTime, int endTime) {
        for (auto &[l, r] : overlaps) {
            if (l < endTime && startTime < r) return false;
        }
        for (auto &[l, r] : booked) {
            if (l < endTime && startTime < r) {
                overlaps.emplace_back(max(l, startTime), min(r, endTime));
            }
        }
        booked.emplace_back(startTime, endTime);
        return true;
    }
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(startTime,endTime);
 */