首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图解LeetCode——731. 我的日程安排表 II(难度:中等)

图解LeetCode——731. 我的日程安排表 II(难度:中等)

作者头像
爪哇缪斯
发布2023-05-10 11:11:35
2550
发布2023-05-10 11:11:35
举报
文章被收录于专栏:爪哇缪斯爪哇缪斯

一、题目

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

MyCalendar 有一个 book(int start, int end)方法。它意味着在 startend 时间内增加一个日程安排,注意,这里的时间是半开区间,即 [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) 时, startend 的取值范围为 [0, 10^9]

三、解题思路

线段树解决的是区间和的问题,且该区间会被修改。所以线段树主要实现两个方法:【求区间和】【修改区间】,且时间复杂度均为 **O(logn)**。

始终记住一句话:线段树的每个节点代表一个区间

既然需要以节点方式展示,并且需要以懒惰标记方式存储值,所以,针对每个节点的数据结构,如下所示:

/** 线段树节点结构 */
class Node {
    Node left; // 左子节点
    Node right; // 右子节点
    int val = 0; // 当前节点值
    int add = 0; // 懒惰标记值
}

什么叫懒惰标记呢? 可以做个比喻。比如我们要将区间[0, 999]这范围内的1000个节点的val值都修改为1,那么我们可以选择把每个叶子节点和区间节点都修改为1,但是这样做,效率会比较低。那么,还有一种方式是,在区间节点[0, 999]的val值修改为1,并且将该节点的add修改为1。那么当遍历到它的子节点的时候,我们再通过节点存储的add值“下移”给子节点,即:[子节点].val += [区间节点].add

我们以安排(10,20)为例,由于默认节点val值为0,所以相关的区间节点都会修改为1。如下是其转换线段树的逻辑:

我们以安排(50,60)为例,由于默认节点val值为0,所以相关的区间节点都会修改为1。如下是其转换线段树的逻辑:

我们以安排(10,40)为例,由于(10,20)已经在上面步骤中被赋值为1了,并且这部分区间是有重叠的,所以相关的区间节点都会修改为2。如下是其转换线段树的逻辑:

我们以安排(5,15)为例,由于(10,20)已经在上面步骤中被赋值为2了,并且这部分区间是有重叠的,所以执行查询方法的时候,查询出在(5,15)中已经有节点为2。那么,如果返回2这个值,则整个插入方法为false,即:无法添加此日程安排。如下是其转换线段树的逻辑:

四、代码实现

4.1> 实现1:线段树 + 懒惰标记

/**
 * 731. 我的日程安排表 II
 */
class MyCalendarTwo {
    private static int START = 0; // 开始区间0
    private static int END = (int) 1e9; // 结束区间10^9
    private static int searchStart = 0; // 待查询的开始区间值
    private static int searchEnd = 0; // 待查询的结束区间值
    private Node root = new Node(); // 创建根节点

    /** 线段树节点结构 */
    class Node {
        Node left; // 左子节点
        Node right; // 右子节点
        int val = 0; // 当前节点值
        int add = 0; // 懒惰标记值
    }

    public MyCalendarTwo() {
    }

    public boolean book(int start, int end) {
        searchStart = start;
        searchEnd = end - 1; // 因为是[start, end),所以end要减1
        if (query(root, START, END) == 2) {
            return false;
        }
        update(root, START, END, 1);
        return true;
    }

    /** 查询某一区间内最大val值 */
    public int query(Node node, int start, int end) {
        // 如果待查询的范围包含了node的范围,则直接返回node.val值
        if (searchStart <= start && end <= searchEnd) {
            return node.val;
        }

        // 如果没有左右子节点,则创建
        pushDown(node);

        int result = 0;
        int middle = (end + start) >> 1; // 取start到end的中间点
        if (searchStart <= middle) {
            result = query(node.left, start, middle);
        }
        if (middle < searchEnd) {
            result = Math.max(result, query(node.right, middle + 1, end));
        }

        return result;
    }

    /** 更新线段树中的相关节点val值 */
    public void update(Node node, int start, int end, int value) {
        if (searchStart <= start && end <= searchEnd) {
            node.val += value;
            node.add += value;
            return;
        }

        // 如果没有左右子节点,则创建
        pushDown(node);

        int middle = (end + start) >> 1; // 取start到end的中间点
        if (searchStart <= middle) {
            update(node.left, start, middle, value);
        }
        if (middle < searchEnd) {
            update(node.right, middle + 1, end, value);
        }
        pushUp(node);
    }

    /** 左右子节点val值的最大值就是父节点val值 */
    public void pushUp(Node node) {
        node.val = Math.max(node.left.val, node.right.val);
    }

    /** 创建左右子节点,并且下移懒惰标记值 */
    public void pushDown(Node node) {
        if (node.left == null) {
            node.left = new Node();
        }
        if (node.right == null) {
            node.right = new Node();
        }
        // 如果懒惰标记值add等于0,则不需要执行下面的【下移懒惰标记值】操作了,直接返回
        if (node.add == 0) {
            return;
        }
        // 【下移懒惰标记值】操作
        node.left.val += node.add;
        node.left.add += node.add;
        node.right.val += node.add;
        node.right.add += node.add;
        node.add = 0;
    }
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2022-07-20,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 爪哇缪斯 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目
  • 二、示例
    • 示例一:
      • 提示:
      • 三、解题思路
      • 四、代码实现
        • 4.1> 实现1:线段树 + 懒惰标记
        相关产品与服务
        对象存储
        对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档