Java实现 LeetCode 732 我的日程安排表 III（暴力 || 二叉树）

待我称王封你为后i 2023-07-24 08:46 15阅读 0赞

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