LeetCode 0435. Non-overlapping Intervals無重疊區(qū)間【Medium】【Python】【區(qū)間貪心】
Problem
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Example 1:
Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Example 2:
Input: [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:
Input: [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
Note:
- You may assume the interval's end point is always bigger than its start point.
- Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
問題
給定一個區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量秉馏，使剩余區(qū)間互不重疊耙旦。
示例 1:
輸入: [ [1,2], [2,3], [3,4], [1,3] ]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊萝究。
示例 2:
輸入: [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個 [1,2] 來使剩下的區(qū)間沒有重疊免都。
示例 3:
輸入: [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區(qū)間，因為它們已經(jīng)是無重疊的了帆竹。
注意:
- 可以認(rèn)為區(qū)間的終點總是大于它的起點绕娘。
- 區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”璃赡，但沒有相互重疊访敌。
思路
區(qū)間貪心
先按左端點從小到大排序，然后 temp_pos 指針指向 i 區(qū)間戒职，當(dāng) temp_pos 指針指向的區(qū)間右端點 > i 區(qū)間左端點，并且 temp_pos 指針指向的區(qū)間右端點 > i 區(qū)間右端點時绢陌，表示當(dāng)前區(qū)間覆蓋范圍大于 i 區(qū)間挨下，因此可以去掉當(dāng)前區(qū)間，保留 i 區(qū)間脐湾，更新 temp_pos 指針臭笆。只要當(dāng) temp_pos 指針指向的區(qū)間右端點 > i 區(qū)間左端點都要計數(shù)+1。當(dāng)當(dāng)前區(qū)間右端點 <= i 區(qū)間左端點秤掌，表示不重疊愁铺，要更新 temp_pos。
時間復(fù)雜度: O(len(intervals))
空間復(fù)雜度: O(1)
Python代碼
class Solution(object):
def eraseOverlapIntervals(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: int
"""
if not intervals or len(intervals) == 0:
return 0
intervals.sort(key = lambda x: x[0]) # 按左端點從小到大排序
temp_pos = 0
cnt = 0
for i in range(1, len(intervals)):
if intervals[temp_pos][1] > intervals[i][0]: # 當(dāng)當(dāng)前區(qū)間右端點>i區(qū)間左端點
if intervals[i][1] < intervals[temp_pos][1]: # 當(dāng)i區(qū)間右端點<當(dāng)前區(qū)間右端點机杜，表示i區(qū)間被覆蓋在當(dāng)前區(qū)間中
temp_pos = i # 更新temp_pos帜讲，選擇覆蓋范圍小的i區(qū)間
cnt += 1 # 當(dāng)前區(qū)間右端點>i區(qū)間左端點都要計數(shù)+1
else:
temp_pos = i # 當(dāng)當(dāng)前區(qū)間右端點<=i區(qū)間左端點，表示不重疊椒拗，要更新temp_pos
return cnt
題外話
網(wǎng)上搜的別人的題解發(fā)現(xiàn)代碼運行都有問題似将，總是提示：'list' object has no attribute 'start' 等錯誤。研究了一下蚀苛，發(fā)現(xiàn)網(wǎng)上題解的代碼開頭都是：
class Solution(object):
def eraseOverlapIntervals(self, intervals):
"""
:type intervals: List[Interval]
:rtype: int
"""
而現(xiàn)在(2020.02.16)此題的代碼開頭是：
class Solution(object):
def eraseOverlapIntervals(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: int
"""
該 intervals 是一個二維列表在验，沒有 start，要按照二維列表來做堵未。照著 LeetCode-0452-用最少數(shù)量的箭引爆氣球 自己寫的題解腋舌，稍微改一下代碼發(fā)現(xiàn)就能 AC 這道題了。
