Re: [閒聊] 每日leetcode

[dont (dont)]

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
```

--
https://i.imgur.com/kyBhy6o.jpeg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.117 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727416367.A.87A.html
→ Rushia: 你板剩我不會刻聖誕樹了