729. My Calendar I
## 思路
複習一下SegmentTree
因為有update區段, 所以加上lazy
不過跑好慢..691ms 不如用SortedList
## Code
```python
class SegmentTree:
def __init__(self):
self.vals = defaultdict(bool)
self.lazy = defaultdict(bool)
def update(self, start, end, left, right, idx):
# no overlap
if start > right or end < left:
return
# fully overlap
if start <= left and right <= end:
self.vals[idx] = True
self.lazy[idx] = True
return
# partial overlap
mid = (left + right) // 2
self.update(start, end, left, mid, idx*2)
self.update(start, end, mid+1, right, idx*2+1)
self.vals[idx] = True
def query(self, start, end, left, right, idx):
# no overlap
if start > right or end < left:
return False
self.push_down(idx)
# fully overlap
if start <= left and right <= end:
return self.vals[idx]
# partial overlap
mid = (left + right) // 2
return self.query(start, end, left, mid, idx*2) or self.query(start,
end, mid+1, right, idx*2+1)
def push_down(self, idx):
if idx not in self.lazy:
return
self.vals[2 * idx] = self.lazy[2 * idx] = self.lazy[idx]
self.vals[2 * idx + 1] = self.lazy[2 * idx + 1] = self.lazy[idx]
del self.lazy[idx]
class MyCalendar:
def __init__(self):
self.events = SegmentTree()
self.size = 10**9 + 1
def book(self, start: int, end: int) -> bool:
has_booked = self.events.query(start, end-1, 0, self.size, 1)
if has_booked:
return False
self.events.update(start, end-1, 0, self.size, 1)
return True
```