前言

線段掃描

• 將數據離散化、排序

• 將線段分成開始事件與結束事件，並分情況處理

• 依照事件發生的時間點( 值)做 iterate，因為同一時刻可能發生多個事件，因此使用 vector 作為 map 的 value，將在時刻 發生的所有事件 push 進 vector 中

• 依情況使用 heap 或是 set 來維護現有的線段

LeetCode 218. The Skyline Problem

• 只關心在對應 x 值的情況下，最高的 y 值為何 ⇒ priority_queue

LeetCode 986. Interval List Intersections

LeetCode 850. Rectangle Area II

• 最完整的線段掃描案例 ⇒ 線段進出事件分別各自處理

• 可將前例(LeetCode 218.)視為每個 x 都存在 y=0 下限之特例

• 使用 multiset 來維護可重複之線段

LeetCode 391. Perfect Rectangle

LeetCode 3433. Count Mentions Per User

• 較為簡單的線段掃描，單純紀錄上下線狀態即可

• 狀態部分處理的順序為 上線 → 下線 → 廣播，否則會錯==

• id 部分給兩種格式(x, idX)，還要特別 parse，超白癡==

LeetCode 3394. Check if Grid can be Cut into Sections

• 分成橫豎兩個方向，判斷能夠切幾刀

• 處理順序: 刪除線段 → 判斷集合大小 → 插入線段

• 宣告 變數，避免在這種情況切超過一刀

• 邊緣部分一定可以滿足區間集合長度為零的條件，因此當作切成四刀以上才滿足題目條件

LeetCode

LeetCode

LeetCode