731. 我的日程安排表 II : 线段树（动态开点）的两种方式

站长

2023年03月25日 16:13 · 阅读数 19

题目描述

这是 LeetCode 上的 731. 我的日程安排表 II ，难度为中等。

Tag : 「线段树（动态开点）」、「线段树」

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end) 方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start,end)[start, end)[start,end), 实数 xxx 的范围为， start<=x<end start <= x < end 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 函数最多不超过 100010001000 次。
调用函数 MyCalendar.book(start, end) 时， start 和 end 的取值范围为 [0,109][0, 10^9][0,109]。

线段树（动态开点）- 估点

和 729. 我的日程安排表 I 几乎完全一致，只需要将对「线段树」所维护的节点信息进行调整即可。

线段树维护的节点信息包括：

ls/rs: 分别代表当前节点的左右子节点在线段树数组 tr 中的下标；
add: 懒标记；
max: 为当前区间的最大值。

对于常规的线段树实现来说，都是一开始就调用 build 操作创建空树，而线段树一般以「满二叉树」的形式用数组存储，因此需要 4×n4 \times n4×n 的空间，并且这些空间在起始 build 空树的时候已经锁死。

如果一道题仅仅是「值域很大」的离线题（提前知晓所有的询问），我们还能通过「离散化」来进行处理，将值域映射到一个小空间去，从而解决 MLE 问题。

但对于本题而言，由于「强制在线」的原因，我们无法进行「离散化」，同时值域大小达到 1e91e91e9 级别，因此如果我们想要使用「线段树」进行求解，只能采取「动态开点」的方式进行。

动态开点的优势在于，不需要事前构造空树，而是在插入操作 add 和查询操作 query 时根据访问需要进行「开点」操作。由于我们不保证查询和插入都是连续的，因此对于父节点 uuu 而言，我们不能通过 u << 1 和 u << 1 | 1 的固定方式进行访问，而要将节点 tr[u]tr[u]tr[u] 的左右节点所在 tr 数组的下标进行存储，分别记为 ls 和 rs 属性。对于 tr[u].ls=0tr[u].ls = 0tr[u].ls=0 和 tr[u].rs=0tr[u].rs = 0tr[u].rs=0 则是代表子节点尚未被创建，当需要访问到它们，而又尚未创建的时候，则将其进行创建。

由于存在「懒标记」，线段树的插入和查询都是 log⁡n\log{n}logn 的，因此我们在单次操作的时候，最多会创建数量级为 log⁡n\log{n}logn 的点，因此空间复杂度为 O(mlog⁡n)O(m\log{n})O(mlogn)，而不是 O(4×n)O(4 \times n)O(4×n)，而开点数的预估需不能仅仅根据 log⁡n\log{n}logn 来进行，还要对常熟进行分析，才能得到准确的点数上界。

动态开点相比于原始的线段树实现，本质仍是使用「满二叉树」的形式进行存储，只不过是按需创建区间，如果我们是按照连续段进行查询或插入，最坏情况下仍然会占到 4×n4 \times n4×n 的空间，因此盲猜 log⁡n\log{n}logn 的常数在 444 左右，保守一点可以直接估算到 666，因此我们可以估算点数为 6×m×log⁡n6 \times m \times \log{n}6×m×logn，其中 n=1e9n = 1e9n=1e9 和 m=1e3m = 1e3m=1e3 分别代表值域大小和查询次数。

当然一个比较实用的估点方式可以「尽可能的多开点数」，利用题目给定的空间上界和我们创建的自定义类（结构体）的大小，尽可能的多开（ Java 的 128M128M128M 可以开到 5×1065 \times 10^65×106 以上）。

Java 代码：

class MyCalendarTwo {
    class Node {
        int ls, rs, add, max;
    }
    int N = (int)1e9, M = 120010, cnt = 1;
    Node[] tr = new Node[M];
    void update(int u, int lc, int rc, int l, int r, int v) {
        if (l <= lc && rc <= r) {
            tr[u].add += v;
            tr[u].max += v;
            return ;
        }
        lazyCreate(u);
        pushdown(u);
        int mid = lc + rc >> 1;
        if (l <= mid) update(tr[u].ls, lc, mid, l, r, v);
        if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, v);
        pushup(u);
    }
    int query(int u, int lc, int rc, int l, int r) {
        if (l <= lc && rc <= r) return tr[u].max;
        lazyCreate(u);
        pushdown(u);
        int mid = lc + rc >> 1, ans = 0;
        if (l <= mid) ans = Math.max(ans, query(tr[u].ls, lc, mid, l, r));
        if (r > mid) ans = Math.max(ans, query(tr[u].rs, mid + 1, rc, l, r));
        return ans;
    }
    void lazyCreate(int u) {
        if (tr[u] == null) tr[u] = new Node();
        if (tr[u].ls == 0) {
            tr[u].ls = ++cnt;
            tr[tr[u].ls] = new Node();
        }
        if (tr[u].rs == 0) {
            tr[u].rs = ++cnt;
            tr[tr[u].rs] = new Node();
        }
    }
    void pushup(int u) {
        tr[u].max = Math.max(tr[tr[u].ls].max, tr[tr[u].rs].max);
    }
    void pushdown(int u) {
        tr[tr[u].ls].add += tr[u].add; tr[tr[u].rs].add += tr[u].add;
        tr[tr[u].ls].max += tr[u].add; tr[tr[u].rs].max += tr[u].add;
        tr[u].add = 0;
    }
    public boolean book(int start, int end) {
        if (query(1, 1, N + 1, start + 1, end) >= 2) return false;
        update(1, 1, N + 1, start + 1, end, 1);
        return true;
    }
}

TypeScript 代码：

class TNode {
    ls: number = 0; rs: number = 0
    max:number = 0; add: number = 0;  
}
class MyCalendarTwo {
    N = 1e9; M = 120010; cnt = 1
    tr: TNode[] = new Array<TNode>(this.M)
    query(u: number, lc: number, rc: number, l: number, r: number): number {
        if (l <= lc && rc <= r) return this.tr[u].max;
        this.pushdown(u)
        let mid = lc + rc >> 1, ans = 0
        if (l <= mid) ans = Math.max(ans, this.query(this.tr[u].ls, lc, mid, l, r))
        if (r > mid) ans = Math.max(ans, this.query(this.tr[u].rs, mid + 1, rc, l, r))
        return ans
    }
    update(u: number, lc: number, rc: number, l: number, r: number, v: number): number {
        if (l <= lc && rc <= r) {
            this.tr[u].add += v
            this.tr[u].max += v
            return 
        }
        this.pushdown(u)
        let mid = lc + rc >> 1
        if (l <= mid) this.update(this.tr[u].ls, lc, mid, l, r, v)
        if (r > mid) this.update(this.tr[u].rs, mid + 1, rc, l, r, v)
        this.pushdup(u)
    }
    pushdown(u: number): void {
        if (this.tr[u] == null) this.tr[u] = new TNode()
        if (this.tr[u].ls == 0) {
            this.tr[u].ls = ++this.cnt
            this.tr[this.tr[u].ls] = new TNode()
        }
        if (this.tr[u].rs == 0) {
            this.tr[u].rs = ++this.cnt
            this.tr[this.tr[u].rs] = new TNode()
        }
        const add = this.tr[u].add
        this.tr[this.tr[u].ls].add += add; this.tr[this.tr[u].rs].add += add
        this.tr[this.tr[u].ls].max += add; this.tr[this.tr[u].rs].max += add
        this.tr[u].add = 0
    }
    pushdup(u: number): void {
        this.tr[u].max = Math.max(this.tr[this.tr[u].ls].max, this.tr[this.tr[u].rs].max)
    }
    book(start: number, end: number): boolean {
        if (this.query(1, 1, this.N + 1, start + 1, end) >= 2) return false
        this.update(1, 1, this.N + 1, start + 1, end, 1)
        return true
    }
}

时间复杂度：令 nnn 为值域大小，本题固定为 1e91e91e9，线段树的查询和增加复杂度均为 O(log⁡n)O(\log{n})O(logn)
空间复杂度：令询问数量为 mmm，复杂度为 O(mlog⁡n)O(m\log{n})O(mlogn)

线段树（动态开点）- 动态指针

利用「动态指针」实现的「动态开点」可以有效避免数组估点问题，更重要的是可以有效避免 new 大数组的初始化开销，对于 LC 这种还跟你算所有样例总时长的 OJ 来说，在不考虑 static 优化/全局数组优化的情况下，动态指针的方式要比估点的方式来得好。

Java 代码：

class MyCalendarTwo {
    class Node {
        Node ls, rs;
        int max, add;
    }
    int N = (int)1e9;
    Node root = new Node();
    void update(Node node, int lc, int rc, int l, int r, int v) {
        if (l <= lc && rc <= r) {
            node.add += v;
            node.max += v;
            return ;
        }
        pushdown(node);
        int mid = lc + rc >> 1;
        if (l <= mid) update(node.ls, lc, mid, l, r, v);
        if (r > mid) update(node.rs, mid + 1, rc, l, r, v);
        pushup(node);
    }
    int query(Node node, int lc, int rc, int l, int r) {
        if (l <= lc && rc <= r) return node.max;
        pushdown(node);
        int mid = lc + rc >> 1, ans = 0;
        if (l <= mid) ans = query(node.ls, lc, mid, l, r);
        if (r > mid) ans = Math.max(ans, query(node.rs, mid + 1, rc, l, r));
        return ans;
    }
    void pushdown(Node node) {
        if (node.ls == null) node.ls = new Node();
        if (node.rs == null) node.rs = new Node();
        int add = node.add;
        node.ls.max += add; node.rs.max += add;
        node.ls.add += add; node.rs.add += add;
        node.add = 0;
    }
    void pushup(Node node) {
        node.max = Math.max(node.ls.max, node.rs.max);
    }
    public boolean book(int start, int end) {
        if (query(root, 0, N, start, end - 1) >= 2) return false;
        update(root, 0, N, start, end - 1, 1);
        return true;
    }
}

TypeScript 代码：

class TNode {
    ls: TNode = null; rs: TNode = null
    max: number = 0; add: number = 0
}
class MyCalendarTwo {
    root: TNode = new TNode()
    update(node: TNode, lc: number, rc: number, l: number, r: number, v: number): void {
        if (l <= lc && rc <= r) {
            node.add += v
            node.max += v
            return 
        }
        this.pushdown(node)
        let mid = lc + rc >> 1
        if (l <= mid) this.update(node.ls, lc, mid, l, r, v)
        if (r > mid) this.update(node.rs, mid + 1, rc, l, r, v)
        this.pushup(node)
    }
    query(node: TNode, lc: number, rc: number, l: number, r: number): number {
        if (l <= lc && rc <= r) return node.max
        let mid = lc + rc >> 1, ans = 0
        this.pushdown(node)
        if (l <= mid) ans = this.query(node.ls, lc, mid, l, r)
        if (r > mid) ans = Math.max(ans, this.query(node.rs, mid + 1, rc, l, r))
        return ans
    }
    pushdown(node: TNode): void {
        if (node.ls == null) node.ls = new TNode()
        if (node.rs == null) node.rs = new TNode()
        const add = node.add
        node.ls.add += add; node.rs.add += add
        node.ls.max += add; node.rs.max += add
        node.add = 0
    }
    pushup(node: TNode): void {
        node.max = Math.max(node.ls.max, node.rs.max)
    }
    book(start: number, end: number): boolean {
        if (this.query(this.root, 0, 1e9, start, end - 1) >= 2) return false
        this.update(this.root, 0, 1e9, start, end - 1, 1)
        return true
    }
}

时间复杂度：令 nnn 为值域大小，本题固定为 1e91e91e9，线段树的查询和增加复杂度均为 O(log⁡n)O(\log{n})O(logn)
空间复杂度：令询问数量为 mmm，复杂度为 O(mlog⁡n)O(m\log{n})O(mlogn)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.731 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

转载自:https://juejin.cn/post/7121934179549478925