731 我的日程安排表 II（线段树-动态开点、模拟）

清疚 2022-09-10 04:21 177阅读 0赞

**1. 问题描述：**

实现一个 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）将和第二个日程安排双重预订。

**提示：**

每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。  
调用函数 MyCalendar.book(start,，end)时， start 和 end 的取值范围为 \[0，10 ^ 9\]。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/my-calendar-ii

**2. 思路分析：**

① 分析题目可以知道这是一道关于**区间修改**与**区间查询**的问题，类似于力扣的[699][]/[715][]题，对于区间修改与区间查询的问题最容易想到的是线段树（线段树适合于求解区间单点修改，区间修改，区间查询的问题）因为涉及到区间修改所以我们可以使用**带有懒标记的线段树**来解决，由题可知我们在维护每一个区间的时候其实维护的是从区间起点到终点的一段连续区间，也即维护的是区间的数值而不是下标，因为区间的起点和终点的最大值为10 \*\* 9，所以我们不能够直接开4n = 4 \* 10 \*\* 9 长度的线段树节数组，这个时候就需要使用**动态开点**的方法来创建对应的线段树节点（一开始的时候不需要声明这么大的线段树节点长度，因为最多调用1000次的book方法所以节点数量肯定小于4 \* 10 \*\* 9），动态开点其实是在将懒标记往下传递，区间修改与区间查询的时候如果需要使用到当前节点的子区间，但是子区间不存在的时候那么需要创建对应的线段树节点，所以这里的线段树写法与之前的写法有点不太一样，之前开这么大的数组然后在查询与修改的时候不用再创建线段树节点直接递归求解即可；这里在区间修改与区间查询的过程中如果子区间的节点不存在那么需要动态创建；怎么样在递归的时候判断子区间是否存在呢？这里借助了Trie树的思想，使用一个全局变量idx来唯一标识每一个线段树节点，这样我们就可以通过在递归的时候判断节点编号对应的线段树节点是否存在即可。每一次查询与修改的时候根节点表示的区间范围为\[1，10 \*\* 9\]，根据区间修改与区间查询的范围决定递归哪一边，在递归的时候判断是否需要创建线段树节点即可。因为使用的是动态开点的方法来编写的所以在调用区间修改与区间查询方法的时候需要传递当前的节点表示的范围\_l，\_r，而当前节点的l与r就可以使用idx的值来唯一标识当前节点的左右子区间的位置。

② 除了线段树的解法之外，因为数据规模不是特别大所以我们可以模拟整个过程来解决，其中需要借助于两个数组或者列表来解决，分别存储重叠一次的区间和重叠两次的区间，一开始的时候先判断\[start，end - 1\]与重叠两次的区间是否有交集如果有直接返回False，如果与重叠两次的区间都没有交集那么遍历重叠一次的区间将\[start，end - 1\]与重叠一次的区间的交集加入到重叠两次的区间中即可。

**3. 代码如下：**

**c++线段树（动态开点）：**

#include<iostream>
    #include<stdio.h>
    using namespace std;
    class MyCalendarTwo {
    public:
        struct node{
            int l, r, sum;
            int add;
        }t[4000005];
        int idx;
        int build(){
            idx++;
            t[idx].l = t[idx].r = t[idx].sum = t[idx].add = 0;
            return idx;
        }
        void updown(int p){
            if(!t[p].l) t[p].l=build();
            if(!t[p].r) t[p].r=build();
            t[t[p].l].sum+=t[p].add;
            t[t[p].r].sum+=t[p].add;
            t[t[p].l].add+=t[p].add;
            t[t[p].r].add+=t[p].add;
            t[p].add=0;
        }
        void add(int p,int l,int r,int L,int R,int x){
            if(l >= L && r <= R){
                t[p].sum += x;
                t[p].add += x;
                return;
            }
            if(t[p].add) updown(p);
            int mid = l + r >> 1;
            if(L <= mid){
                if(!t[p].l)  t[p].l= build();
                add(t[p].l, l, mid, L, R, x);
            }
            if(R > mid){
                if(!t[p].r) t[p].r = build();
                add(t[p].r, mid + 1, r, L, R, x);
            }
            t[p].sum = max(t[t[p].l].sum, t[t[p].r].sum);
        }
        int query(int p, int l, int r, int L, int R){
            if(l >= L && r<= R){
                return t[p].sum;
            }
            if(t[p].add) updown(p);
            int v = 0;
            int mid = l + r >> 1;
            if(L <= mid){
                if(!t[p].l)  t[p].l = build();
                v = max(v,query(t[p].l, l, mid, L, R));
            }
            if(R>mid){
                if(!t[p].r) t[p].r=build();
                v = max(v, query(t[p].r, mid + 1, r, L, R));
            }
            return v;
        }
        int root;
        MyCalendarTwo() {
            idx = 0;
            root = build();
        }
        bool book(int start, int end) {
            if(query(root, 0, 1e9, start, end-1) >= 2) return false;
            add(root, 0, 1e9, start, end-1, 1);
            return true;
        }
    };

**java线段树（超时）：感觉java主要是初始化对象数组的时候比较耗时，一般操作次数比较多的时候对象数组长度为10 \*\* 3的时候蔡可任意通过。**

public class MyCalendarTwo {
        // 下面采用的是线段树的另外一种写法, 类似于之前的Trie使用idx来唯一标识线段树每一个节点
        static Tree []tr;
        // 使用idx唯一标识每一个节点
        static int idx = 0;
    
        // 创建线段树的节点, 使用idx来唯一标识当前的线段树节点
        public static int build(){
            idx++;
            tr[idx].l = tr[idx].r = tr[idx].sum = tr[idx].add = 0;
            return idx;
        }
    
        // 由子节点的信息计算父节点的信息, 计算区间的最大值即可, 表示当前区间使用使用次数的那个数
        public static void pushup(int u){
            tr[u].sum = Math.max(tr[tr[u].l].sum, tr[tr[u].r].sum);
        }
        
        // 将父节点的懒标记下传到子节点
        public static void pushdown(int u){
            if (tr[u].l == 0) tr[u].l = build();
            if (tr[u].r == 0) tr[u].r = build();
            int v = tr[u].add;
            tr[tr[u].l].add += v;
            tr[tr[u].r].add += v;
            tr[tr[u].l].sum += v;
            tr[tr[u].r].sum += v;
            tr[u].add = 0;
        }
        
        // _l, _r表示当前节点的节点表示的区间范围
        public static void modify(int u, int _l, int _r, int l, int r, int v){
            if (_l >= l && _r <= r){
                // 当前节点的区间包含在查询区间的范围内
                tr[u].sum += v;
                tr[u].add += v;
                return;
            }
            if (tr[u].add != 0) pushdown(u);
            int mid = _l + _r >> 1;
            // 判断当前的mid与l的关系判断是否存在交集
            if (l <= mid){
                // 判断当前节点是否存在不存在则创建对应的节点
                if (tr[u].l == 0){
                    tr[u].l = build();
                }
                modify(tr[u].l, _l, mid, l, r, v);
            }
            if (r > mid){
                if (tr[u].r == 0){
                    tr[u].r = build();
                }
                modify(tr[u].r, mid + 1, _r, l, r, v);
            }
            // 修改了区间之后那么需要执行pushup操作
            pushup(u);
        }
    
        // 查询操作
        public static int query(int u, int _l, int _r, int l, int r){
            if (_l >= l && _r <= r) return tr[u].sum;
            if (tr[u].add != 0) pushdown(u);
            int mid = _l + _r >> 1;
            int res = 0;
            if (l <= mid){
                if (tr[u].l == 0) tr[u].l = build();
                res = Math.max(res, query(tr[u].l, _l, mid, l, r));
            }
            if (r > mid){
                if (tr[u].r == 0) tr[u].r = build();
                res = Math.max(res, query(tr[u].r, mid + 1, _r, l, r));
            }
            return res;
        }
    
        public MyCalendarTwo() {
            tr = new Tree[4000005];
            // 初始化线段树的每一个节点
            for (int i = 0; i < tr.length; ++i){
                tr[i] = new Tree();
            }
            // 创建根节点
            build();
        }
    
        public static boolean book(int start, int end) {
            // 根节点的区间为[1, 10 ** 9], 根据
            int res = query(1, 1, 1000000000, start, end - 1);
            if (res >= 2) return false;
            modify(1, 1, 1000000000, start, end - 1, 1);
            return true;
        }
    
        public static class Tree{
            private int l, r;
            private int sum, add;
        }
    }

**模拟（python）：**

class MyCalendarTwo:
        def __init__(self):
            # 使用两个列表分别记录重叠两次的区间overlaps与重叠一次calendars 的区间
            self.calendars = list()
            self.overlaps = list()
    
        def book(self, start: int, end: int) -> bool:
            # 首先是end减1
            end -= 1
            calendars = self.calendars
            overlaps = self.overlaps
            for t in overlaps:
                s = max(start, t[0])
                e = min(end, t[1])
                # 其实画图很容易理解, 当s <= e的时候是存在交集的
                if s <= e: return False
            # 将重叠的部分插入到重叠的列表
            for t in calendars:
                s = max(start, t[0])
                e = min(end, t[1])
                if s <= e:
                    # 将有交集的区间添加到重叠两次的区间中
                    overlaps.append([s, e])
            # 添加上当前的区间
            calendars.append([start, end])
            return True

[699]: https://blog.csdn.net/qq_39445165/article/details/119519803
[715]: https://blog.csdn.net/qq_39445165/article/details/120011538