golang刷leetcode 技巧（7） 我的日程安排表 I
golang刷leetcode 技巧（7） 我的日程安排表 I
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 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。
说明:
每个测试用例，调用 MyCalendar.book 函数最多不超过 100次。
调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。解题思路1:
1，暴力解法
2，每次插入的时候存入一个有序的list
3，如果能插入则成功
4，否则是失败的
代码实现1：
type MyCalendar struct {
ts [][]int
}
func Constructor() MyCalendar {
return MyCalendar{}
}
func (this *MyCalendar) Book(start int, end int) bool {
if len(this.ts)==0{
this.ts=append(this.ts,[]int{start,end})
return true
}
if end <=this.ts[0][0]{
this.ts=append([][]int{[]int{start,end}},this.ts...)
return true
}
if start>=this.ts[len(this.ts)-1][1]{
this.ts=append(this.ts,[]int{start,end})
return true
}
index:=0
for i:=1;i<len(this.ts);i++{
if this.ts[i][1]>start{
index=i-1
break
}
}
if this.ts[index][1]<=start &&this.ts[index+1][0]>=end{
t:=append(this.ts[:index+1:index+1],[]int{start,end})
this.ts=append(t,this.ts[index+1:]...)
return true
}
return false
}
/**
* Your MyCalendar object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/解题思路2:
1.构造线段树节点。
2.新添加的线段树节点，要么只能全在node.start往左，要么只能全在node.end往右。
3.左右子树如果不存在，这表示该区间不存在，可以插入，如果存在，则往其左右子树递推即可。
4.不满足条件的则表示与当前节点的区间发生了重叠，不能插入。
代码实现2
type MyCalendar struct {
root *Node
}
type Node struct{
start int
end int
left *Node
right *Node
}
func Constructor() MyCalendar {
return MyCalendar{}
}
func (this *MyCalendar) Book(start int, end int) bool {
if this.root==nil{
this.root=&Node{start:start,end:end}
return true
}
n:=this.root
for true{
if end<=n.start{
if n.left==nil{
n.left=&Node{start:start,end:end}
return true
}
n=n.left
}else if start>=n.end{
if n.right==nil{
n.right=&Node{start:start,end:end}
return true
}
n=n.right
}else{
return false
}
}
return false
}
/**
* Your MyCalendar object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
