实现一个 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）将和第二个日程安排双重预订。
class MyCalendarTwo {
public MyCalendarTwo() {
}
public boolean book(int start, int end) {
if (query(root, 0, N, start, end - 1) == 2) {
return false;
}
update(root, 0, N, start, end - 1, 1);
return true;
}
class Node {
Node left;
Node right;
int val;
int add;
}
int N = Integer.MAX_VALUE;
Node root = new Node();
void update(Node node, int start, int end, int l, int r, int val) {
if (l <= start && r >= end) {
node.val += val;
node.add += val;
return;
}
pushDown(node);
int mid = (start + end) / 2;
if (l <= mid) update(node.left, start, mid, l, r, val);
if (r > mid) update(node.right, mid + 1, end, l, r, val);
pushUp(node);
}
int query(Node node, int start, int end, int l, int r) {
if (l <= start && r >= end) {
return node.val;
}
pushDown(node);
int mid = (start + end) / 2;
int ans = 0;
if (l <= mid) ans = query(node.left, start, mid, l, r);
if (r > mid) ans = Math.max(ans, query(node.right, mid + 1, end, l, r));
return ans;
}
void pushUp(Node node) {
node.val = Math.max(node.left.val, node.right.val);
}
void pushDown(Node node) {
if (node.left == null) {
node.left = new Node();
}
if (node.right == null) {
node.right = new Node();
}
if (node.add == 0) {
return;
}
node.left.add += node.add;
node.right.add += node.add;
node.left.val += node.add;
node.right.val += node.add;
node.add = 0;
}
}
标记一下，找时间补一下线段树的课。