題目出處
435. Non-overlapping Intervals
難度
Medium
個人範例程式碼
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key = lambda x: x[1])
cnt = 0
end = float("-inf")
for i, interval in enumerate(intervals):
if interval[0] >= end:
end = interval[1] # update end
else:
cnt += 1
return cnt
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
算法說明
這題我們使用的是 greedy 的作法,
我們先依照 end 來排序,
依據 greedy 的策略,我們把初始 end 設定為 -inf,
- 正常情況:如果每一次 start >= 前一個 end (表示無重疊),且因為我們已經先將 end 排序,因此可以視為得到所有以 end 開頭的區間。
- 異常情況:start 比前一個 end 小,表示重疊了,此時我們 ans += 1,然後 continue 不理這一組 (視為會被刪掉的組合)
input handling
一同在 for loop 內處理。
Boundary conditions
用 for loop 控制範圍
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) | Python | 內有 indegree, outdegree 介紹 #重要題型 | ||
207 | Course Schedule | BFS (拓樸) | Graph | Python | ||
210 | Course Schedule II | BFS (拓樸) | Graph | Python | ||
[Lint] 892 | Alien Dictionary | BFS (拓樸) | Graph | Python | ||
[Lint] 431 | Connected Component in Undirected Graph | BFS (連通塊) | Graph | Python | 內含 BFS 模板 #重要題型 | |
1091 | Shortest Path in Binary Matrix | BFS (最短路徑) | Matrix | Python | ||
⭐ Binary Serach 相關題型 ⭐ | ||||||
33 | Search in Rotated Sorted Array |