729. 我的日程安排表 I
实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。
当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。
日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end 。
实现 MyCalendar 类：
MyCalendar() 初始化日历对象。boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。
示例：
输入： ["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]] 输出： [null, true, false, true] 解释： MyCalendar myCalendar = new MyCalendar(); myCalendar.book(10, 20); // return True myCalendar.book(15, 25); // return False ，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。 myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20 ，且不包含时间 20 。
提示：
0 <= start < end <= 109book 方法的次数最多不超过 1000 次。原站题解
golang 解法, 执行用时: 144 ms, 内存消耗: 7.6 MB, 提交时间: 2022-11-21 10:04:57
type MyCalendar struct {
tree, lazy map[int]bool
}
func Constructor() MyCalendar {
return MyCalendar{map[int]bool{}, map[int]bool{}}
}
func (c MyCalendar) query(start, end, l, r, idx int) bool {
if r < start || end < l {
return false
}
if c.lazy[idx] { // 如果该区间已被预订，则直接返回
return true
}
if start <= l && r <= end {
return c.tree[idx]
}
mid := (l + r) >> 1
return c.query(start, end, l, mid, 2*idx) ||
c.query(start, end, mid+1, r, 2*idx+1)
}
func (c MyCalendar) update(start, end, l, r, idx int) {
if r < start || end < l {
return
}
if start <= l && r <= end {
c.tree[idx] = true
c.lazy[idx] = true
} else {
mid := (l + r) >> 1
c.update(start, end, l, mid, 2*idx)
c.update(start, end, mid+1, r, 2*idx+1)
c.tree[idx] = true
if c.lazy[2*idx] && c.lazy[2*idx+1] {
c.lazy[idx] = true
}
}
}
func (c MyCalendar) Book(start, end int) bool {
if c.query(start, end-1, 0, 1e9, 1) {
return false
}
c.update(start, end-1, 0, 1e9, 1)
return true
}
/**
* Your MyCalendar object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/
python3 解法, 执行用时: 940 ms, 内存消耗: 19.7 MB, 提交时间: 2022-11-21 10:04:04
class MyCalendar:
def __init__(self):
self.tree = set()
self.lazy = set()
def query(self, start: int, end: int, l: int, r: int, idx: int) -> bool:
if r < start or end < l:
return False
if idx in self.lazy: # 如果该区间已被预订，则直接返回
return True
if start <= l and r <= end:
return idx in self.tree
mid = (l + r) // 2
return self.query(start, end, l, mid, 2 * idx) or \
self.query(start, end, mid + 1, r, 2 * idx + 1)
def update(self, start: int, end: int, l: int, r: int, idx: int) -> None:
if r < start or end < l:
return
if start <= l and r <= end:
self.tree.add(idx)
self.lazy.add(idx)
else:
mid = (l + r) // 2
self.update(start, end, l, mid, 2 * idx)
self.update(start, end, mid + 1, r, 2 * idx + 1)
self.tree.add(idx)
if 2 * idx in self.lazy and 2 * idx + 1 in self.lazy:
self.lazy.add(idx)
def book(self, start: int, end: int) -> bool:
if self.query(start, end - 1, 0, 10 ** 9, 1):
return False
self.update(start, end - 1, 0, 10 ** 9, 1)
return True
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)
python3 解法, 执行用时: 224 ms, 内存消耗: 16.3 MB, 提交时间: 2022-11-21 10:02:51
from sortedcontainers import SortedDict
class MyCalendar:
def __init__(self):
self.booked = SortedDict()
def book(self, start: int, end: int) -> bool:
i = self.booked.bisect_left(end)
if i == 0 or self.booked.items()[i - 1][1] <= start:
self.booked[start] = end
return True
return False
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)
golang 解法, 执行用时: 60 ms, 内存消耗: 7.1 MB, 提交时间: 2022-11-21 10:01:55
type MyCalendar struct {
*redblacktree.Tree
}
func Constructor() MyCalendar {
t := redblacktree.NewWithIntComparator()
t.Put(math.MaxInt32, nil) // 哨兵，简化代码
return MyCalendar{t}
}
func (c MyCalendar) Book(start, end int) bool {
node, _ := c.Ceiling(end)
it := c.IteratorAt(node)
if !it.Prev() || it.Value().(int) <= start {
c.Put(start, end)
return true
}
return false
}
/**
* Your MyCalendar object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/
golang 解法, 执行用时: 68 ms, 内存消耗: 7 MB, 提交时间: 2022-11-21 10:00:23
type pair struct{ start, end int }
type MyCalendar []pair
func Constructor() MyCalendar {
return MyCalendar{}
}
func (c *MyCalendar) Book(start, end int) bool {
for _, p := range *c {
if p.start < end && start < p.end {
return false
}
}
*c = append(*c, pair{start, end})
return true
}
/**
* Your MyCalendar object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/
python3 解法, 执行用时: 680 ms, 内存消耗: 15.8 MB, 提交时间: 2022-11-21 10:00:06
class MyCalendar:
def __init__(self):
self.booked = []
def book(self, start: int, end: int) -> bool:
if any(l < end and start < r for l, r in self.booked):
return False
self.booked.append((start, end))
return True
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)