710 - Python LeetCode

【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