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);
*/