題目
給定一個(gè)區(qū)間的集合 intervals 媳叨，其中 intervals[i] = [starti, endi] 。返回需要移除區(qū)間的最小數(shù)量关顷，使剩余區(qū)間互不重疊糊秆。
例：
輸入: intervals = [[1,2],[2,3],[3,4],[1,3]]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區(qū)間沒(méi)有重疊议双。
方法：貪心算法
按照右邊界的大小進(jìn)行從小到大的排序痘番，為了盡可能的得到少的移除區(qū)間，應(yīng)該選擇右邊界小的元素平痰，右邊界越小那么留給下一個(gè)區(qū)間的空間就越大
- 若集合中不存在任何區(qū)間夫偶，那么沒(méi)有需要移除的區(qū)間界睁，返回零
- 按照有邊界進(jìn)行從小到大的排序
- count 表示非交叉區(qū)間的個(gè)數(shù)，若想要求得移除區(qū)間的最小值兵拢，只需要用集合的數(shù)量減去非交叉區(qū)間的個(gè)數(shù)即可翻斟。end 表示區(qū)間的分界點(diǎn)
- 從左到右循環(huán)遍歷集合，起始值為 1说铃，因?yàn)榈谝粋€(gè)非交叉區(qū)間一定是集合的第一個(gè)區(qū)間访惜。若此區(qū)間的起始值大于 end，表示兩個(gè)區(qū)間并不相交腻扇，此區(qū)間不需要被移除债热，則 count + 1，同時(shí)更新 end 為此區(qū)間的右邊界
class Solution(object):
def eraseOverlapIntervals(self, intervals):
if len(intervals) == 0:
return 0
intervals.sort(key = lambda x:(x[1]))
count = 1
end = intervals[0][1]
for i in range(1, len(intervals)):
if end <= intervals[i][0]:
count += 1
end = intervals[i][1]
return len(intervals) - count
參考
代碼相關(guān)：https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html
