給定一個區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。

注意:

可以認為區(qū)間的終點總是大于它的起點。
區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。
示例 1:

輸入: [ [1,2], [2,3], [3,4], [1,3] ]

輸出: 1

解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。

代碼

class Solution {public int eraseOverlapIntervals(int[][] intervals) {if(intervals.length==0) return 0;Arrays.sort(intervals,((o1, o2) -> o1[1]-o2[1]));//按區(qū)間末尾大小升序int end=intervals[0][1];int cnt=0;for(int i=0;i<intervals.length;i++){if(intervals[i][0]<end)//與前面的區(qū)間重疊了{cnt++;continue;}end=intervals[i][1];//新的結(jié)尾}return cnt-1;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode435. 无重叠区间（贪心算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。