https://leetcode.com/problems/my-calendar-i/
看了左神课之后,自己实现了下改造后的线段树(非常不优雅),因为数组放不下,所以自建 Node 结构。
class Node {
int l;
int r;
boolean used; // 当前范围已全覆盖
Node left;
Node right;
public Node(int l, int r) {
this.l = l;
this.r = r;
}
}
class MyCalendar {
Node info;
public MyCalendar() {
info = new Node(0, 1 << 30);
}
public boolean book(int start, int end) {
if (canAdd(info, start, end - 1)) { // [左闭,右闭]区间
add(info, start, end - 1);
return true;
} else {
return false;
}
}
public boolean canAdd(Node info, int L, int R) {
if (info.used) return false;
// 当前范围从未开垦且可以全覆盖,则不分发直接返回
if (info.left == null && L <= info.l && info.right == null && R >= info.r - 1) return true;
// 分发至左右子树
int m = (info.l + info.r) / 2;
if (L < m) {
if (info.left != null && !canAdd(info.left, L, R)) return false;
}
if (R >= m) {
if (info.right != null && !canAdd(info.right, L, R)) return false;
}
return true;
}
public void add(Node node, int L, int R) {
if (L <= node.l && R >= node.r - 1) {
node.used = true;
return;
}
// 分发至左右子树
int m = (node.l + node.r) / 2;
if (L < m) {
if (node.left == null) {
node.left = new Node(node.l, m);
}
add(node.left, L, R);
}
if (R >= m) {
if (node.right == null) {
node.right = new Node(m, node.r);
}
add(node.right, L, R);
}
}
}
/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/sinat_42483341/article/details/121438282
内容来源于网络,如有侵权,请联系作者删除!