732. 我的日程安排表 III
实现一个 MyCalendar 类来存放你的日程安排，你可以一直添加新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。它意味着在start到end时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。
当 K 个日程安排有一些时间上的交叉时（例如K个日程安排都在同一时间内），就会产生 K 次预订。
每次调用 MyCalendar.book方法时，返回一个整数 K ，表示最大的 K 次预订。
请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
示例 1:
MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
解释:
前两个日程安排可以预订并且不相交，所以最大的K次预订是1。
第三个日程安排[10,40]与第一个日程安排相交，最高的K次预订为2。
其余的日程安排的最高K次预订仅为3。
请注意，最后一次日程安排可能会导致局部最高K次预订为2，但答案仍然是3，原因是从开始到最后，时间[10,20]，[10,40]和[5,15]仍然会导致3次预订。
说明:
每个测试用例，调用 MyCalendar.book 函数最多不超过 400次。
调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。
PS:
暴力
class MyCalendarThree {
private TreeMap<Integer, Integer> calendar;
public MyCalendarThree() {
calendar = new TreeMap<>();
}
public int book(int start, int end) {
// 添加至日程中
calendar.put(start, calendar.getOrDefault(start, 0) + 1);
calendar.put(end, calendar.getOrDefault(end, 0) - 1);
// 记录最大活跃的日程数
int max = 0;
// 记录活跃的日程数
int active = 0;
for (Integer d : calendar.values()) {
// 以时间线统计日程
active += d;
// 找到活跃事件数量最多的时刻，记录下来。
if (active > max) {
max = active;
}
}
return max;
}
}
/**
* Your MyCalendarThree object will be instantiated and called as such:
* MyCalendarThree obj = new MyCalendarThree();
* int param_1 = obj.book(start,end);
*/
PS：
二叉树
class MyCalendarThree {
public static class SegmentTree {
public static class Node {
private int lo;
private int hi;
private int range;
private int maxCover = 0;
private int lazy = 0;
private Node left;
private Node right;
public Node(int lo, int hi) {
this.lo = lo;
this.hi = hi;
this.range = hi - lo;
}
}
Node root = null;
public int addRange(int qLo, int qHi) {
checkRoot(qLo, qHi);
update(root, qLo, qHi, 1);
return root.maxCover;
}
private void update(Node root, int qLo, int qHi, int diff) {
if (root == null) {
return;
}
checkLazy(root);
if (qHi <= root.lo || root.hi <= qLo) {
return;
}
checkChildren(root);
if (qLo <= root.lo && root.hi <= qHi) {
root.maxCover += diff;
if (root.left != null) {
root.left.lazy += diff;
}
if (root.right != null) {
root.right.lazy += diff;
}
return;
}
update(root.left, qLo, qHi, diff);
update(root.right, qLo, qHi, diff);
root.maxCover = Math.max(root.left.maxCover, root.right.maxCover);
}
private void checkChildren(Node root) {
if (root.range <= 1) {
return;
}
if (root.left != null && root.right != null) {
return;
}
int mid = root.lo + (root.hi - root.lo) / 2;
if (root.left == null) {
int r = root.right == null ? mid : root.right.lo;
root.left = new Node(root.lo, r);
}
if (root.right == null) {
root.right = new Node(root.left.hi, root.hi);
}
}
private void checkLazy(Node root) {
if (root.lazy == 0) {
return;
}
root.maxCover += root.lazy;
checkChildren(root);
//propagation
if (root.left != null) {
root.left.lazy += root.lazy;
root.right.lazy += root.lazy;
}
//reset lazy
root.lazy = 0;
}
private void checkRoot(int qLo, int qHi) {
if (root == null) {
root = new Node(qLo, qHi);
return;
}
while (qHi > root.hi) {
Node newR = new Node(root.lo, Math.min(1000000000, root.hi + root.range));
newR.left = root;
newR.maxCover=root.maxCover;
root = newR;
}
while (qLo < root.lo) {
Node newR = new Node(Math.max(0, root.lo - root.range), root.hi);
newR.right = root;
newR.maxCover=root.maxCover;
root = newR;
}
}
}
SegmentTree st = new SegmentTree();
public MyCalendarThree() {
}
public int book(int start, int end) {
return st.addRange(start, end);
}
}
/**
* Your MyCalendarThree object will be instantiated and called as such:
* MyCalendarThree obj = new MyCalendarThree();
* int param_1 = obj.book(start,end);
*/