Re: [閒聊] 每日leetcode

看板Marginalman作者dont (dont)時間1年前 (2024/09/26 21:14)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串911/1554 (看更多)

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