第一題
- 難度：中等
- 題目：435. 無重疊區(qū)間
給定一個(gè)區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量靶壮，使剩余區(qū)間互不重疊怔毛。
注意:
可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。
區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”腾降，但沒有相互重疊拣度。
示例
輸入: [ [1,2], [2,3], [3,4], [1,3] ]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊蜂莉。
輸入: [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個(gè) [1,2] 來使剩下的區(qū)間沒有重疊蜡娶。
輸入: [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區(qū)間，因?yàn)樗鼈円呀?jīng)是無重疊的了映穗。
解題思路
- 這道題使用貪心算法窖张，先把數(shù)組按最后的數(shù)排序，然后依次比較最后的數(shù)是否都大于flag否則就是重復(fù)元素
我的答案
var eraseOverlapIntervals = function (intervals) {
if (!intervals.length) return 0
intervals.sort((a, b) => { return a[1] - b[1] })
let flag = intervals[0][1];
let count = 0
for (let i = 1; i <= intervals.length - 1; i++) {
if (flag > intervals[i][0]) {
count += 1
} else {
flag = intervals[i][1]
}
}
return count
};
image.png
