@ninijia 在 Leetcode每日一题练习 ------ 729. 我的日程安排表 I 中发帖
从Leetcode 每日一题练习继续讨论:
729. 我的日程安排表 I
729. My Calendar I
题解
本题涉及到区间问题,可以使用线段树。在熟悉线段树结构的情况下本题非常容易解决,只需查询book中出现的区间在线段树中查询得到的区间和是否为0即可知道该区间是否被覆盖过,如果为0说明区间完全没有被覆盖则可以预订,并更新对应区间的值,这里可以给区间所有值加一(在线段树中这个操作并不会真的将全部节点都加1,而是会存在懒操作,只要在覆盖这个区间的节点内加入标记记录了存在加1操作)。非0则区间可能被部分覆盖,即有冲突,则不能预订。
关键的部分在线段树的实现,这里我们使用动态开点的线段树并使用懒标记。
代码
class MyCalendar {
private:
struct Node {
Node* left;
Node* right...