731. My Calendar II
## 思路
改写昨天的扣, 检查区段最大值
别人写的SegmentTree都好快 唉
另一种写法是直接存intervals (book1次) 跟overlaps (book2次)
检查(start,end)跟两个array有无重叠
## Code
```python
class SegmentTree:
def __init__(self):
self.vals = defaultdict(int)
self.lazy = defaultdict(int)
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] += 1
self.lazy[idx] += 1
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] = self.lazy[idx] + max(self.vals[idx*2],
self.vals[idx*2+1])
def query(self, start, end, left, right, idx):
# no overlap
if start > right or end < left:
return 0
self.push_down(idx)
# fully overlap
if start <= left and right <= end:
return self.vals[idx]
# partial overlap
mid = (left + right) // 2
return max(self.query(start, end, left, mid, idx*2),
self.query(start, end, mid+1, right, idx*2+1))
def push_down(self, idx):
if idx not in self.lazy:
return
self.vals[idx*2] += self.lazy[idx]
self.vals[idx*2+1] += self.lazy[idx]
self.lazy[idx*2] += self.lazy[idx]
self.lazy[idx*2+1] += self.lazy[idx]
del self.lazy[idx]
class MyCalendarTwo:
def __init__(self):
self.events = SegmentTree()
self.size = 10**9 + 1
def book(self, start: int, end: int) -> bool:
max_booked = self.events.query(start, end-1, 0, self.size, 1)
if max_booked >= 2:
return False
self.events.update(start, end-1, 0, self.size, 1)
return True
```
```python
class MyCalendarTwo:
def __init__(self):
self.intervals = []
self.overlaps = []
def book(self, start: int, end: int) -> bool:
for p_start, p_end in self.overlaps:
if not (start >= p_end or end <= p_start):
return False
for p_start, p_end in self.intervals:
if not (start >= p_end or end <= p_start):
self.overlaps.append((max(start, p_start), min(end, p_end)))
self.intervals.append((start, end))
return True
```