Medium

题目描述

你正在实现一个用作日程安排表的程序。如果添加事件不会造成三重预订，则可以添加新事件。

当三个事件具有一些非空交集时（即，某个时刻对所有三个事件都是共同的），就会发生三重预订。

事件可以表示为一对整数 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，而时间 10 已经被双重预订。
myCalendarTwo.book(25, 55); // 返回 True，事件可以被预订。

约束条件：

  • 0 <= start < end <= 10^9
  • 最多调用 book 1000 次。

解题思路

解题思路

这道题要求我们实现一个日程安排表，允许双重预订但不允许三重预订。核心思想是维护两个列表：

  1. 单次预订列表（calendar）：记录所有成功预订的事件
  2. 双重预订列表（overlaps）：记录所有重叠区间（已经双重预订的时间段）

算法流程：

  1. 当有新事件要预订时，首先检查它是否与已有的双重预订区间重叠
  2. 如果与双重预订区间重叠，说明会产生三重预订，返回 false
  3. 如果没有三重预订，则检查新事件与单次预订的重叠情况：
    • 将所有重叠部分加入双重预订列表
    • 将新事件加入单次预订列表

重叠区间计算：

两个区间 [start1, end1) 和 [start2, end2) 的重叠部分为：

  • 起始时间：max(start1, start2)
  • 结束时间：min(end1, end2)
  • 重叠条件：起始时间 < 结束时间

这种方法的时间复杂度为 O(n)，其中 n 是已预订事件的数量，空间复杂度为 O(n)。

代码实现

class MyCalendarTwo {
private:
    vector<pair<int, int>> calendar;
    vector<pair<int, int>> overlaps;
    
public:
    MyCalendarTwo() {
        
    }
    
    bool book(int startTime, int endTime) {
        // 检查是否与双重预订区间重叠（会造成三重预订）
        for (auto& overlap : overlaps) {
            if (max(startTime, overlap.first) < min(endTime, overlap.second)) {
                return false;
            }
        }
        
        // 检查与单次预订的重叠，添加到双重预订列表
        for (auto& event : calendar) {
            int overlapStart = max(startTime, event.first);
            int overlapEnd = min(endTime, event.second);
            if (overlapStart < overlapEnd) {
                overlaps.push_back({overlapStart, overlapEnd});
            }
        }
        
        // 添加到单次预订列表
        calendar.push_back({startTime, endTime});
        return true;
    }
};

class MyCalendarTwo:

    def __init__(self):
        self.calendar = []
        self.overlaps = []

    def book(self, startTime: int, endTime: int) -> bool:
        # 检查是否与双重预订区间重叠（会造成三重预订）
        for start, end in self.overlaps:
            if max(startTime, start) < min(endTime, end):
                return False
        
        # 检查与单次预订的重叠，添加到双重预订列表
        for start, end in self.calendar:
            overlap_start = max(startTime, start)
            overlap_end = min(endTime, end)
            if overlap_start < overlap_end:
                self.overlaps.append((overlap_start, overlap_end))
        
        # 添加到单次预订列表
        self.calendar.append((startTime, endTime))
        return True

public class MyCalendarTwo {
    private List<(int start, int end)> calendar;
    private List<(int start, int end)> overlaps;

    public MyCalendarTwo() {
        calendar = new List<(int, int)>();
        overlaps = new List<(int, int)>();
    }
    
    public bool Book(int startTime, int endTime) {
        // 检查是否与双重预订区间重叠（会造成三重预订）
        foreach (var overlap in overlaps) {
            if (Math.Max(startTime, overlap.start) < Math.Min(endTime, overlap.end)) {
                return false;
            }
        }
        
        // 检查与单次预订的重叠，添加到双重预订列表
        foreach (var evt in calendar) {
            int overlapStart = Math.Max(startTime, evt.start);
            int overlapEnd = Math.Min(endTime, evt.end);
            if (overlapStart < overlapEnd) {
                overlaps.Add((overlapStart, overlapEnd));
            }
        }
        
        // 添加到单次预订列表
        calendar.Add((startTime, endTime));
        return true;
    }
}

var MyCalendarTwo = function() {
    this.calendar = [];
    this.overlaps = [];
};

MyCalendarTwo.prototype.book = function(startTime, endTime) {
    // 检查是否与双重预订区间重叠（会造成三重预订）
    for (let overlap of this.overlaps) {
        if (Math.max(startTime, overlap[0]) < Math.min(endTime, overlap[1])) {
            return false;
        }
    }
    
    // 检查与单次预订的重叠，添加到双重预订列表
    for (let event of this.calendar) {
        let overlapStart = Math.max(startTime, event[0]);
        let overlapEnd = Math.min(endTime, event[1]);
        if (overlapStart < overlapEnd) {
            this.overlaps.push([overlapStart, overlapEnd]);
        }
    }
    
    // 添加到单次预订列表
    this.calendar.push([startTime, endTime]);
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每次book操作需要遍历已有的预订事件和重叠区间，n为已预订事件数量
空间复杂度O(n)需要存储所有预订事件和重叠区间，最坏情况下重叠区间数量为O(n²)

相关题目