leetcode刷題之線段樹惰性傳播

2019 年 10 月 6 日
筆記

leetcode刷題之線段樹惰性傳播

0.導語

今天刷題難度為困難，題目是：我的日程安排表 III，題號是732。

本節則主要採用圖與樹這兩種數據結構解決本題。

樹指的是我從來沒聽過的線段樹。方法是Lazy Propagation in Segment Tree(線段樹的惰性傳播)。

1.題目

實現一個 MyCalendar 類來存放你的日程安排，你可以一直添加新的日程安排。

MyCalendar 有一個 book(int start, int end)方法。它意味着在start到end時間內增加一個日程安排，注意，這裡的時間是半開區間，即 [start, end), 實數 x 的範圍為， start <= x < end。

當 K 個日程安排有一些時間上的交叉時（例如K個日程安排都在同一時間內），就會產生 K 次預訂。

每次調用 MyCalendar.book方法時，返回一個整數 K ，表示最大的 K 次預訂。

請按照以下步驟調用MyCalendar 類: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例 1:

MyCalendarThree();  MyCalendarThree.book(10, 20); // returns 1  MyCalendarThree.book(50, 60); // returns 1  MyCalendarThree.book(10, 40); // returns 2  MyCalendarThree.book(5, 15); // returns 3  MyCalendarThree.book(5, 10); // returns 3  MyCalendarThree.book(25, 55); // returns 3  解釋:  前兩個日程安排可以預訂並且不相交，所以最大的K次預訂是1。  第三個日程安排[10,40]與第一個日程安排相交，最高的K次預訂為2。  其餘的日程安排的最高K次預訂僅為3。  請注意，最後一次日程安排可能會導致局部最高K次預訂為2，但答案仍然是3，原因是從開始到最後，時間[10,20]，[10,40]和[5,15]仍然會導致3次預訂。

說明:

每個測試用例，調用 MyCalendar.book 函數最多不超過 400次。
調用函數 MyCalendar.book(start, end)時， start 和 end 的取值範圍為 [0, 10^9]。

2.圖方法

【思路】

根據上述實例與題意，我們知道只需要關注起點與終點，而不需要關注中間過程，節點的出度個數就是最終結果。

【實現】

import collections  class MyCalendarThree:      def __init__(self):          self.book_dict = collections.defaultdict(int)        def book(self, start: 'int', end: 'int') -> 'int':          self.book_dict[start]+=1          self.book_dict[end]-=1          # 出度          outdegree = 0          tmpMax = 0          for k,v in sorted(self.book_dict.items()):              outdegree+=v              if tmpMax<outdegree:                  tmpMax=outdegree          return tmpMax

3.線段樹的惰性傳播

【思想】

什麼是線段樹？參考自：https://www.jianshu.com/p/e00c95951cd2

線段樹也是一種數據結構，我也是第一次聽說，不過這個非常好理解。

線段樹是一種二叉搜索樹，又叫區間樹，它將一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉結點，根節點存儲的是左右孩子節點範圍的和。

那什麼是惰性傳播呢？

對於這個惰性傳播，這裡給出一個YouTube視頻，講的非常棒。

這道題的另外一種解法就是Lazy Propagation in Segment Tree(線段樹的惰性傳播)。這個方法來源於leetcode的disscuss中，如下鏈接。

https://leetcode.com/problems/my-calendar-iii/discuss/214831/Python-13-Lines-Segment-Tree-with-Lazy-Propagation-O(1)-time

【實現】

惰性傳播，(惰性樹中)非零則更新原樹。

import collections  class MyCalendarThree(object):        def __init__(self):          # 節點值          self.seg = collections.defaultdict(int)          # 惰性樹存儲的當前節點值          self.lazy = collections.defaultdict(int)        def book(self, start, end):          def update(s, e, l = 0, r = 10**9, ID = 1):              if r <= s or e <= l: return              # 區間滿足所給的start到end範圍              if s <= l < r <= e:                  self.seg[ID] += 1                  self.lazy[ID] += 1              else:                  # 折半更新區間段                  m = (l + r) // 2                  update(s, e, l, m, 2 * ID)                  update(s, e, m, r, 2*ID+1)                  # 更新當前節點，通過惰性樹中的值與左右孩子值進行更新。                  self.seg[ID] = self.lazy[ID] + max(self.seg[2*ID], self.seg[2*ID+1])          update(start, end)          return self.seg[1]

這個算法是個遞歸算法，通過遞歸，最後的結果就會更新到第一個節點，所以直接返回第一個節點值就是最終結果。