項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [435] Non-overlapping Intervals 個人解法筆記

題目出處

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 SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)Python
內有 indegree, outdegree 介紹 #重要題型
207Course ScheduleBFS (拓樸)GraphPython
210Course Schedule IIBFS (拓樸)GraphPython
[Lint] 892Alien DictionaryBFS (拓樸)GraphPython
[Lint] 431Connected Component in Undirected GraphBFS (連通塊)GraphPython 內含 BFS 模板 #重要題型
1091Shortest Path in Binary MatrixBFS (最短路徑)MatrixPython
⭐ Binary Serach 相關題型 ⭐
33Search in Rotated Sorted Array