推 sustainer123: 最近怎麼那麼難 哭了 09/26 21:43
→ dont: 要簡單寫也可以用binary tree或是internal+binary search 09/27 01:07
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
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.231 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727356455.A.F56.html