leetcode 729 731 732. My Calendar I II III | 729. 我的日程安排表 I II III（线段树）

729. My Calendar I

/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);*/

731. My Calendar II

/problems/my-calendar-ii/

class Node {int l;int r;int lazy; // 当前范围懒增加数量Node left; // 左闭区间Node right; // 右开区间public Node(int l, int r) {this.l = l;this.r = r;}}class MyCalendarTwo {Node node;public MyCalendarTwo() {node = new Node(0, 1 << 30);}public boolean book(int start, int end) {if (canAdd(node, start, end - 1)) {// [左闭,右闭]区间add(node, start, end - 1, 1);return true;} else {return false;}}public boolean canAdd(Node node, int L, int R) {if (node.lazy == 2) return false;// 当前范围从未开垦且可以全覆盖，则不分发直接返回if (node.left == null && L <= node.l && node.right == null && R >= node.r - 1) return true;// 分发至左右子树pushDown(node);int m = (node.l + node.r) / 2;if (L < m) {if (node.left != null && !canAdd(node.left, L, R)) return false;}if (R >= m) {if (node.right != null && !canAdd(node.right, L, R)) return false;}return true;}public void add(Node node, int L, int R, int val) {if (L <= node.l && R >= node.r - 1) {node.lazy += val;return;}// 分发至左右子树pushDown(node);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, val);}if (R >= m) {if (node.right == null) {node.right = new Node(m, node.r);}add(node.right, L, R, val);}}private void pushDown(Node node) {int m = (node.l + node.r) / 2;if (node.l < node.r) {if (node.left == null) {node.left = new Node(node.l, m);}node.left.lazy += node.lazy;if (node.right == null) {node.right = new Node(m, node.r);}node.right.lazy += node.lazy;node.lazy = 0;}}}

732. My Calendar III

/problems/my-calendar-iii/

class Node {int l;int r;int lazy; // 当前范围懒增加数量Node left; // 左闭区间Node right; // 右开区间public Node(int l, int r) {this.l = l;this.r = r;}}class MyCalendarThree {Node node;int result;public MyCalendarThree() {result = 0;node = new Node(0, 1 << 30);}public int book(int start, int end) {add(node, start, end - 1, 1); // [start, end-1]result = Math.max(result, getMax(node, start, end - 1));return result;}public int getMax(Node node, int L, int R) {// 当前范围未开垦且可以全覆盖，则不分发直接返回if (node.left == null && L <= node.l && node.right == null && R >= node.r - 1) return node.lazy;// 分发至左右子树pushDown(node);int m = (node.l + node.r) / 2;int leftMax = 0;if (L < m && node.left != null) {leftMax = getMax(node.left, L, R);}int rightMax = 0;if (R >= m && node.right != null) {rightMax = getMax(node.right, L, R);}return Math.max(leftMax, rightMax);}public void add(Node node, int L, int R, int val) {if (L <= node.l && R >= node.r - 1) {node.lazy += val;return;}// 分发至左右子树pushDown(node);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, val);}if (R >= m) {if (node.right == null) {node.right = new Node(m, node.r);}add(node.right, L, R, val);}}private void pushDown(Node node) {int m = (node.l + node.r) / 2;if (node.l < node.r) {if (node.left == null) {node.left = new Node(node.l, m);}node.left.lazy += node.lazy;if (node.right == null) {node.right = new Node(m, node.r);}node.right.lazy += node.lazy;node.lazy = 0;}}}