剑指 Offer II 058. 日程表
请实现一个 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)
示例:
输入: ["MyCalendar","book","book","book"] [[],[10,20],[15,25],[20,30]] 输出: [null,true,false,true] 解释: MyCalendar myCalendar = new MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(15, 25); // returns false ，第二个日程安排不能添加到日历中，因为时间 15 已经被第一个日程安排预定了 MyCalendar.book(20, 30); // returns true ，第三个日程安排可以添加到日历中，因为第一个日程安排并不包含时间 20
提示：
MyCalendar.book 函数最多不超过 1000次。0 <= start < end <= 109
注意：本题与主站 729 题相同： https://leetcode.cn/problems/my-calendar-i/
原站题解
golang 解法, 执行用时: 152 ms, 内存消耗: 7.6 MB, 提交时间: 2022-11-21 10:06:37
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 解法, 执行用时: 956 ms, 内存消耗: 19.7 MB, 提交时间: 2022-11-21 10:06:13
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 解法, 执行用时: 232 ms, 内存消耗: 16.2 MB, 提交时间: 2022-11-21 10:02:38
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 解法, 执行用时: 68 ms, 内存消耗: 7.1 MB, 提交时间: 2022-11-21 10:01:45
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 解法, 执行用时: 76 ms, 内存消耗: 7 MB, 提交时间: 2022-11-21 10:00:33
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 解法, 执行用时: 556 ms, 内存消耗: 15.9 MB, 提交时间: 2022-11-21 09:59:26
'''
直接遍历
'''
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)