Skip to main content

我的日程安排表-i

Tips

题目类型: 线段树

题目​

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

当两个日程安排有一些时间上的交叉时(例如两个日程安排都在同一时间内), 就会产生重复预订.

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

实现 MyCalendar 类:

  • MyCalendar() 初始化日历对象.
  • boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订, 返回 true.否则, 返回 false 并且不要将该日程安排添加到日历中.
示例
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.

题解​

var MyCalendar = function () {
  this.books = []
}

/**
 * @param {number} start
 * @param {number} end
 * @return {boolean}
 */
MyCalendar.prototype.book = function (start, end) {
  for (const book of this.books) {
    const [s, e] = book
    if (s < end && start < e) {
      return false
    }
  }

  this.books.push([start, end])
  return true
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * var obj = new MyCalendar()
 * var param_1 = obj.book(start,end)
 */

  • 时间复杂度: O(n2), 其中 n 表示日程安排的数量. 由于每次在进行预订时, 都需要遍历所有已经预订的行程安排.

  • 空间复杂度: O(n), 其中 n 表示日程安排的数量. 需要保存所有已经预订的行程.