我的日程安排表I

发表于 分类于

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/my-calendar-i

题目

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。

日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end 。

实现 MyCalendar 类：

  • MyCalendar() 初始化日历对象。
  • boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。

思路

直接用一个递增的数组存放安排时间，然后遍历找到可以插入的位置，即上一个结束时间在我的开始时间之前，下一个开始时间在我的结束时间之后。

提交！通过！easy！不对，怎么要耗时141ms，这句数据量不是只有1000吗？

开始优化，数组是递增的，用优先队列？不行，插入虽然是按时间排序插入，但是要判断条件。那就既然是有序的数组，那就二分查找，耗时19ms，90.48%，还行。

看看题解，直接遍历，二分，线段树。好熟悉的名词，好像在打算法的大佬舍友那里听过，看一眼。

我们直接维护一个线段树，book时查询区间是否有值，有返回false，没有返回ture。
线段树直接套模板，线段树详解

线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点，使用线段树可以快速的对区间进行修改和查询。