likes
comments
collection
share

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

作者站长头像
站长
· 阅读数 18

题目描述

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

Tag : 「线段树(动态开点)」、「线段树」

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

MyCalendar 有一个 book(int start, int end) 方法。它意味着在 startend 时间内增加一个日程安排,注意,这里的时间是半开区间,即 [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 << 1u << 1 | 1 的固定方式进行访问,而要将节点 tr[u]tr[u]tr[u] 的左右节点所在 tr 数组的下标进行存储,分别记为 lsrs 属性。对于 tr[u].ls=0tr[u].ls = 0tr[u].ls=0tr[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=1e9m=1e3m = 1e3m=1e3 分别代表值域大小和查询次数。

当然一个比较实用的估点方式可以「尽可能的多开点数」,利用题目给定的空间上界和我们创建的自定义类(结构体)的大小,尽可能的多开( Java128M128M128M 可以开到 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
评论
请登录