729. My Calendar I
请实作一个日历
我们可以增加一个事件
如果这个事件跟已经存在的事件日期尚没有重叠
一个事件的开始日期跟另一个事件的结束日期可以重叠
思路:
就照做
用一个dates表示目前的事件
每次都用binary search(针对start)去找应该插入在哪里
假设binary search 找到的位置是idx
那有3种情况是不允许的
1.dates[idx]的start跟要插入的start相同
2.dates[idx-1]的end比要插入的start还大
3.dates[idx]的start小于要插入的end
除上述三种情况外，都是合法的
把合法的事件加入dates里
这样就可以实作了
golang code :
type MyCalendar struct {
dates [][2]int
}
func Constructor() MyCalendar {
return MyCalendar{[][2]int{{-1,-1},{math.MaxInt64, math.MaxInt64}}}
}
func (this *MyCalendar) Book(start int, end int) bool {
date := [2]int{start, end}
if len(this.dates) == 1 {
this.dates = append([][2]int{date}, this.dates...)
return true
}
idx := this.bs(date)
if date[0]==this.dates[idx][0] || date[0] < this.dates[idx-1][1] || date[1] >
this.dates[idx][0] {
return false
} else {
this.dates = append(this.dates[:idx], append([][2]int{date}, this.dates[idx:
]...)...)
return true
}
}
func (this *MyCalendar) bs(date [2]int) int {
r := len(this.dates)
l := 0
for r > l {
m := l + (r-l)/2
if date[0] > this.dates[m][0] {
l = m + 1
} else {
r = m
}
}
return l
}
/**
* Your MyCalendar object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/
/**
* Your MyCalendar object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/