题目名称

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

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。

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

每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
解释：
前两个日程安排可以添加至日历中。 第三个日程安排会导致双重预订，但可以添加至日历中。
第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。
第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。
第六个日程安排（25,55）可以添加至日历中，因为时间 [25,40] 将和第三个日程安排双重预订；
时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。

题解

暴力计算法

  • 算法思想解析

    最简单的一种方法就是暴力计算法，直接遍历已有的日历时间，然后计算出时间中两次重叠的时间区间，每次添加新的日历时，查看时间区间是否包含在两次重叠的时间区间内，如果包含在里面，则会造成三重重叠，不可添加进日历，如果不包含，则可以添加到日历，此时需要重新计算双重重叠的区间

  • 算法步骤解析

    首先我们需要创建一个 MyCalendarTwo 函数，并且定义日历数组（calenderList）和双重重复区间数组（doubleList）

    在函数实例上创建 添加日历方法（book）

    方法内部首先会去遍历双重重复区间数组，然后对比时间区间是否在双重区间内，只有不在双重区间内才可通过，否则返回false

    具体对比方法其实就像两条线段，如果想要两条线段有重叠，只需要满足一个条件即可 其中一条线段的最右边的点一定是大于另一条线段的最左边的点，且最左边的点一定是小于另一条线段最右边的点

    接下来就是和日历中的时间进行比较，计算出所有双重重叠区间，然后将新添加的时间区间添加到日历数组中

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var MyCalendarTwo = function() {
    this.calenderList = []
    this.doubleList = []
};
MyCalendarTwo.prototype.book = function(start, end) {
    for(let i = 0; i < this.doubleList.length; i++) {
        let l = this.doubleList[i][0], r = this.doubleList[i][1]
        if (end > l && start < r) {
            return false
        }
    }
    for(let i = 0; i < this.calenderList.length; i++) {
        let l = this.calenderList[i][0], r = this.calenderList[i][1]
        if (end > l && start < r) {
            this.doubleList.push([Math.max(l, start), Math.min(r, end)])
        }
    }
    this.calenderList.push([start, end])
    return false
};