My Calendar的book方法实现指定开始时间、结束时间，在重叠次数要求不同的情况下怎么实现。

729 My Calendar I 要求任意两个事件之间不能重叠。如果要插入的事件和已经插入的事件不重叠，则插入；否则不插入。

731 MyCalendar II 要求任意三个时间之间不能重叠，但两个事件可以重叠。同样，如果满足要求，则事件可以插入，否则不能插入。

732 MyCalendar III 则是要求返回插入当前事件之后，整个Calendar中重叠次数最多是多少。

729 My Calendar I

要求任意两个事件之间不能重叠，可以利用二叉查找树BST。每个节点代表一个事件，包含start，end。如果要插入的事件范围，全部在当前节点左侧，或者右侧，则可以插入。否则不可以插入。

class MyCalendarV3 {class Node{int start,end;Node left,right;Node(int start,int end){this.start = start;this.end = end;}}Node root;public boolean book(int start, int end) {if(insertable(start,end,root)){root = insert(start,end,root);return true;}return false;}private Node insert(int start, int end, Node cur) {if(cur==null) return new Node(start,end);if(start>=cur.end) {cur.right = insert(start, end, cur.right);}else if(end <= cur.start) {cur.left = insert(start, end, cur.left);}return cur;}private boolean insertable(int start, int end, Node cur) {if(cur==null) return true;if(start>=cur.end) {return insertable(start, end, cur.right);}else if(end <= cur.start) {return insertable(start, end, cur.left);}return false;}}

731 My Calendar II

要求任意三个时间之间不能重叠，但两个事件可以重叠。在上面解题的基础上，需要将有重叠区域的做节点分裂，并且标记是不是已经重复。如果已经重复的节点，再次遇到重叠，则不允许插入。这个节点分裂，则是整个过程中比较复杂的部分。

例如：MyCalendar.book(10, 20); MyCalendar.book(50, 60); 之后树应该是这样的。

当要插入(10,40)的时候，首先会遇到与curNode(10,20)节点重叠。节点分裂为[10,10),[10,20),[20,40)三个部分。[10,10)插入curNode的左节点，[20,40)插入curNode的右节点。在插入右节点的时候又需要与已经存在的右节点(50,60)做比较。[20,40)作为节点(50,60)的左节点插入。如下图所示。节点(10,20)被标记为overlap=true。下次再碰到这个区域的重叠的事件，则可以直接返回false。

当然节点[10,10)是没有意义的。既包含10，又不包含10，是空集应该去掉。

以上展示了一个节点分裂的过程。插入的start，end；当前节点的curNode.left，curNode.right，这四个数之间有大小关系。如果按照从小到大分别记为n1,n2,n3,n4，则(n1,n2)是curNode的左子树；(n3,n4)作为curNode的右子树；curNode.left=n2,curNode.right=n3。

class MyCalendarTwoV2 {class Node{int start,end;boolean overlap;Node left,right;Node(int start,int end){this.start = start;this.end = end;}}Node root;public MyCalendarTwoV2() {}public boolean book(int start, int end) {if(!insertable(start,end,root)){return false;}root = insert(start,end,root);return true;}private Node insert(int start, int end, Node cur) {if(start>=end) return cur;if(cur==null){return new Node(start,end);}if(start >= cur.end) {cur.right = insert(start,end,cur.right);}else if(end <= cur.start){cur.left = insert(start,end,cur.left);}else{cur.overlap = true;int a = Math.min(start, cur.start);int b = Math.max(start, cur.start);int c = Math.min(end, cur.end);int d = Math.max(end, cur.end);cur.left = insert(a,b,cur.left);cur.right = insert(c,d,cur.right);cur.start = b;cur.end = c;}return cur;}/*** 判断start，end 是否可插入* @param start* @param end* @param curNode* @return*/private boolean insertable(int start, int end, Node cur) {if(start>=end) return true;if(cur==null) return true;if(start >= cur.end) {return insertable(start,end,cur.right);}else if(end <= cur.start){return insertable(start,end,cur.left);}else{if(cur.overlap){return false;}else{if(start>=cur.start && end <= cur.end){return true;}else{return insertable(start,cur.start,cur.left) && insertable(cur.end,end,cur.right);}}}}}

732 My Calendar III

要求返回插入当前事件之后，整个Calendar中重叠次数最多是多少。在上题基础上，把Boolean 变量换成计数的int类型。当本区域发生一次重叠，则计数加1。

对于分裂产生的节点，次数不能简单设置为1。

参考上图，分析一下分裂插入的左子树部分。假设curNode当前区域已经出现了count次。如果分裂后的区域是[start,curNode.left)这是一个新的区域，次数为1；如果分裂后是[curNode.left,start)那么次数就应该是count，因为[curNode.left,start)肯定包含在[curNode.left,curNode.right)范围内。同理分析一下右子树部分。

class MyCalendarThree {class Node{int start,end;int k = 1;Node left,right;Node(int start,int end,int k){this.start = start;this.end = end;this.k = k;}}Node root;int maxK=1;public MyCalendarThree() {}/*** * @param start* @param end* @return*/public int book(int start, int end) {root = insert(start,end,root,1);return maxK;}private Node insert(int start, int end, Node cur,int val) {if (start >= end)return cur;if (cur == null) {return new Node(start, end,val);}if (start >= cur.end) {cur.right = insert(start, end, cur.right,val);} else if (end <= cur.start) {cur.left = insert(start, end, cur.left,val);} else {int a = Math.min(start, cur.start);int b = Math.max(start, cur.start);int c = Math.min(end, cur.end);int d = Math.max(end, cur.end);//细节是这里cur.left = insert(a, b, cur.left,start<=cur.start?val:cur.k);cur.right = insert(c, d, cur.right,end>=cur.end?val:cur.k);cur.start = b;cur.end = c;cur.k +=val;}maxK = Math.max(maxK, cur.k);return cur;}}

My Calendar的其他思路

BST只是一种解决思路。还可以使用其他。例如729 可以使用TreeMap，判断重叠区域。731 可以在利用729类的基础上，判断是否有重叠区域。732还有一种timeline的思路。把所有区域看做是一条线上的点。这种思路非常赞。遇到start，值加1；遇到end，值减1。求得在一个线段内重复的次数。

例如：MyCalendarThree.book(10, 20); // returns 1

MyCalendarThree.book(50, 60); // returns 1

MyCalendarThree.book(10, 40); // returns 2

[10,20)2次

[20,40)1次

[40,50)0次

[50,60)1次

class MyCalendarThreeV2 {private TreeMap<Integer, Integer> timeline = new TreeMap<>();public int book(int s, int e) {timeline.put(s, (timeline.get(s)!=null?timeline.get(s):0) + 1); // 1 new event will be// starting at [s]timeline.put(e, (timeline.get(e)!=null?timeline.get(e):0) - 1); // 1 new event will be// ending at [e];int ongoing = 0, k = 0;for (int v : timeline.values())k = Math.max(k, ongoing += v);return k;}}

参考资料：

网页1

网页2

网页3

网页4

如果觉得《用BST解决729. My Calendar I 731. My Calendar II 732. My Calendar III》对你有帮助，请点赞、收藏，并留下你的观点哦！