我的日程安排表
729 我的日程安排表 I
难度中等
实现一个 MyCalendar
类来存放你的日程安排。如果要添加的时间内没有其他安排,则可以存储这个新的日程安排。
MyCalendar
有一个 book(int start, int end)
方法。它意味着在 start 到 end 时间内增加一个日程安排,注意,这里的时间是半开区间,即 [start, end)
, 实数 x
的范围为, start <= x < end
。
当两个日程安排有一些时间上的交叉时(例如两个日程安排都在同一时间内),就会产生重复预订。
每次调用 MyCalendar.book
方法时,如果可以将日程安排成功添加到日历中而不会导致重复预订,返回 true
。否则,返回 false
并且不要将该日程安排添加到日历中。
请按照以下步骤调用 MyCalendar
类: MyCalendar cal = new MyCalendar();
MyCalendar.book(start, end)
示例 1:
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
解释:
第一个日程安排可以添加到日历中. 第二个日程安排不能添加到日历中,因为时间 15 已经被第一个日程安排预定了。
第三个日程安排可以添加到日历中,因为第一个日程安排并不包含时间 20 。
说明:
- 每个测试用例,调用
MyCalendar.book
函数最多不超过100
次。 - 调用函数
MyCalendar.book(start, end)
时,start
和end
的取值范围为[0, 10^9]
。
分析
共三个解法,从朴素实现开始逐步优化。
朴素实现
用一个集合来存储不断添加的日程;每次添加需要确定已有日程是否和要添加的日程有重叠 集合可以用list或切片;查找需要遍历集合,插入可以简单在末尾追加 假设已有日程有n个,时间复杂度为O(n),空间复杂度为集合的大小,O(n)
type Interval struct {
start, end int
}
type MyCalendar struct {
calendar *list.List
}
func Constructor() MyCalendar {
return MyCalendar{calendar: list.New()}
}
func (mc *MyCalendar) Book(start int, end int) bool {
for e := mc.calendar.Front(); e != nil; e = e.Next() {
interval := e.Value.(Interval)
if max(start, interval.start) < min(end, interval.end) {
return false
}
}
mc.calendar.PushBack(Interval{start:start, end:end})
return true
}
func max(a, b int) int {
return int(math.Max(float64(a), float64(b)))
}
func min(a, b int) int {
return int(math.Min(float64(a), float64(b)))
}
维持列表有序
可以维持集合里的日程有序(可依据每个日程的开始时间排序),每次插入新日程就可以用二分法迅速判读是否有重叠,同时要插入的位置。 用list或堆(优先队列)的话,查找用不了二分法,这里可用切片,查找要插入的位置时间复杂度为O(lgn),插入的话,因为要把待插入位置及其后边元素一一后移,时间复杂度是O(n)——实际上二分只是对判读是否重叠有用,如果只是尝试插入,不如直接从列表最后一一向前确定位置。 综合最坏情况时间复杂度、空间复杂度与朴素实现相同,为O(n);但是在普遍情况下要比朴素实现快
3.BST 优化
在插入新日程的时候,如果集合用切片,则有一一向后移动元素的复杂度在, 有没有一个数据结构能在常数时间插入元素,还能保证元素有序, 且能在常数时间查询任意索引元素从而能用二分法做查询呢? 堆、list和切片都不行 二叉搜索树BST可堪此任,不过如果插入的顺序比较特别,bst会退化成一个链表 实际需要一个能维持平衡的搜索树,比如红黑树,像Java有TreeMap可用, Go标准库并没有这样的数据结构,手动实现起来有些复杂,暂不尝试 仅朴素BST来一把 时间复杂度最坏O(n^2), 平均情况O(nlgn);空间复杂度O(n)
```go
type Node struct {
left, right *Node
start, end int
}
func (n *Node) insert(node *Node) bool {
if node.start >= n.end {
if n.right == nil {
n.right = node
return true
}
return n.right.insert(node)
}
if node.end <= n.start {
if n.left == nil {
n.left = node
return true
}
return n.left.insert(node)
}
return false
}
type MyCalendar struct {
root *Node
}
func Constructor() MyCalendar {
return MyCalendar{}
}
func (mc *MyCalendar) Book(start int, end int) bool {
node := &Node{start:start, end:end}
if mc.root == nil {
mc.root = node
return true
}
return mc.root.insert(node)
}
实际测试,朴素BST的实现比朴素实现好一点,但是不比切片的实现好。
731. 我的日程安排表 II
与上面的问题类似,但是这次允许日程有所重叠:
当三个日程安排有一些时间上的交叉时(例如三个日程安排都在同一时间内),就会产生三重预订。
每次调用 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)时, start 和 end 的取值范围为 [0, 10^9]。
朴素实现
解决方法与上面的问题类似,除了calendar,可以另外增加一个集合存储双重预定重合的部分,不妨称其为overlap 新插入日程时,先遍历overlap看看有没有和overlap重叠,有则返回false, 否则插入calendar且注意与calendar有重叠需要同步往overlap里追加下
时空复杂度都是O(n)
type interval struct {
start, end int
}
type MyCalendarTwo struct {
calendar, overlap []interval // 分别表示已经添加的所有日程和已有日程重复的时间段组成的列表
}
func Constructor() MyCalendarTwo {
return MyCalendarTwo{}
}
func (mc *MyCalendarTwo) Book(start int, end int) bool {
for _, val := range mc.overlap {
if start < val.end && end > val.start {
return false
}
}
for _, val := range mc.calendar {
if start < val.end && end > val.start {
it := interval{start: max(start, val.start), end: min(end, val.end)}
mc.overlap = append(mc.overlap, it)
}
}
it := interval{start: start, end: end}
mc.calendar = append(mc.calendar, it)
return true
}
func max(a, b int) int {
return int(math.Max(float64(a), float64(b)))
}
func min(a, b int) int {
return int(math.Min(float64(a), float64(b)))
}
二分法优化
尝试用二分法优化朴素实现 要稍微复杂点,寻找要插入的位置用二分法; 但是在统计新日程和已有日程的重叠部分的时候,还是要从头遍历calendar,因为有可能一个区间跨越了多个区间 时空复杂度都是O(n) 实际测试并没有明显优化,还是需要一个类似红黑树的数据结构啊~
type interval struct {
start, end int
}
type MyCalendarTwo struct {
// 分别表示已经添加的所有日程和已有日程重复的时间段组成的列表
calendar, overlap []interval
}
func Constructor() MyCalendarTwo {
return MyCalendarTwo{}
}
func (mc *MyCalendarTwo) Book(start int, end int) bool {
if len(mc.overlap) > 0 {
// 二分搜索出新日程在overlap里的位置,不存在的话找需要插入的位置
pos := sort.Search(len(mc.overlap), func(i int) bool {
return mc.overlap[i].start >= start
})
// 查看搜索出的位置附件有没有和当前日程重叠的部分
if pos < len(mc.overlap) && mc.overlap[pos].start < end ||
pos-1 >= 0 && mc.overlap[pos-1].end > start {
return false
}
}
for _, v := range mc.calendar {
if max(v.start, start) < min(v.end, end) {
it := interval{start: max(start, v.start), end: min(end, v.end)}
pos := sort.Search(len(mc.overlap), func(i int) bool {
return mc.overlap[i].start >= it.start
})
// 在pos处插入it
mc.overlap = append(append(mc.overlap[:pos:pos], it), mc.overlap[pos:]...)
}
}
pos := sort.Search(len(mc.calendar), func(i int) bool {
return mc.calendar[i].start >= start
})
it := interval{start: start, end: end}
// 在pos处插入it
mc.calendar = append(append(mc.calendar[:pos:pos], it), mc.calendar[pos:]...)
return true
}
func max(a, b int) int {
return int(math.Max(float64(a), float64(b)))
}
func min(a, b int) int {
return int(math.Min(float64(a), float64(b)))
}
732. 我的日程安排表 III
这次不再限制日程重叠度,放开限制随便加日程,但是每次加完要返回一个整数K,表示最大的 K 次预订。
当 K 个日程安排有一些时间上的交叉时(例如K个日程安排都在同一时间内),就会产生 K 次预订。
每次调用 MyCalendar.book方法时,返回一个整数 K ,表示最大的 K 次预订。
请按照以下步骤调用MyCalendar 类:
MyCalendar cal = new MyCalendar();
MyCalendar.book(start, end)
示例 1:
MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
解释:
前两个日程安排可以预订并且不相交,所以最大的K次预订是1。
第三个日程安排[10,40]与第一个日程安排相交,最高的K次预订为2。
其余的日程安排的最高K次预订仅为3。
请注意,最后一次日程安排可能会导致局部最高K次预订为2,但答案仍然是3,
原因是从开始到最后,时间[10,20],[10,40]和[5,15]仍然会导致3次预订。
说明:
每个测试用例,调用 MyCalendar.book 函数最多不超过 400次。
调用函数 MyCalendar.book(start, end)时, start 和 end 的取值范围为 [0, 10^9]。
朴素实现
按照时间点来统计: 把原问题想象成在数轴上画线段,如果线段有重合,则重合的部分颜色加深 所幸我们关注的点都是整数。对于数轴上每个点,统计其被多少条线段覆盖,可为点增加一个深度的属性来记录 为了能在常数时间插入点,可用list 时空复杂度都是O(n)
type point struct {
pos int // 该点在数轴上的位置。
deep int // 该点的深度——即被多少条线段包含。
}
type MyCalendarThree struct {
points *list.List
k int
}
func Constructor() MyCalendarThree {
mc := MyCalendarThree{points: list.New()}
// 结合list特点, 方便后续处理,先预置两个点,无限小点和和无限大点
// 注意输入的start和end在范围[0, 10^9]内
mc.points.PushBack(&point{pos: -1, deep: 0})
mc.points.PushBack(&point{pos: 1e9 + 1, deep: 0})
return mc
}
func (mc *MyCalendarThree) Book(start int, end int) int {
var startNode, endNode *list.Element
// 插入起始点,如果已经存在则不插入
for e := mc.points.Front(); e.Next() != nil; e = e.Next() {
p := e.Value.(*point)
if start == p.pos {
startNode = e
break
}
// 插入点,注意其深度暂时和其前驱点深度一致
nextP := e.Next().Value.(*point)
if start > p.pos && start < nextP.pos {
p := &point{pos: start, deep: p.deep}
startNode = mc.points.InsertAfter(p, e)
break
}
}
// 插入结束点,如果已经存在则不插入
for e := mc.points.Back(); e.Prev() != nil; e = e.Prev() {
p := e.Value.(*point)
if end == p.pos {
endNode = e
break
}
prevP := e.Prev().Value.(*point)
if end < p.pos && end > prevP.pos {
p := &point{pos: end, deep: prevP.deep}
endNode = mc.points.InsertBefore(p, e)
break
}
}
// 对于起始和结束点之间的所有点,深度都加一。
for e := startNode; e != endNode && e != nil; e = e.Next() {
p := e.Value.(*point)
p.deep++
mc.k = max(mc.k, p.deep)
}
return mc.k
}
func max(a, b int) int {
if a > b {
return a
}
return b
}