困难

问题描述

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

给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

• MyCalendarThree() 初始化对象。
• int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

示例：

输入：
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, 1, 1, 2, 3, 3, 3]

解释：
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

提示：

• 0 <= start < end <= 109
• 每个测试用例，调用 book 函数最多不超过 400 次

差分数组

利用差分数组的思想，当预定一个新的日程安排 $[start,end)$，$start$ 的计数加 $1$，表示从 $start$ 开始，预定数目增加 $1$。$end$ 的计数减 $1$，表示从 $end$ 开始，预定数目减少 $1$。最终对计数进行累加，求出最大的预定数。因为数据范围比较大，所以使用离散化存储。

var MyCalendarThree = function () {
  this.bookings = []
}

/**
 * @param {number} start
 * @param {number} end
 * @return {number}
 */
MyCalendarThree.prototype.book = function (start, end) {
  this.bookings.push([start, 1])
  this.bookings.push([end, -1])
  this.bookings.sort((a, b) => a[0] - b[0] || a[1] - b[1])
  let ans = 0
  let cnt = 0
  this.bookings.forEach((item) => {
    cnt += item[1]
    ans = Math.max(cnt, ans)
  })
  return ans
}

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

• 时间复杂度：$O(n^2)$，每次查询都要遍历一次，$n$ 次查询就是 $n^2$
• 空间复杂度：$O(n)$