題目鏈接

Leetcode-435：無重疊區間

題目描述

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

注意:

可以認為區間的終點總是大于它的起點。

區間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。

示例 1:

輸入: [ [1,2], [2,3], [3,4], [1,3] ]輸出: 1解釋: 移除 [1,3] 后，剩下的區間沒有重疊。

示例 2:

輸入: [ [1,2], [1,2], [1,2] ]輸出: 2解釋: 你需要移除兩個 [1,2] 來使剩下的區間沒有重疊。

示例 3:

輸入: [ [1,2], [2,3] ]輸出: 0解釋: 你不需要移除任何區間，因為它們已經是無重疊的了。

解題思路

貪心算法，將區間按照終點由小到大排序，進行一次遍歷。

在遍歷中記錄終點值，當出現一個新的區間的時候，如果這個值大于現有終點，則可以加入這個區間，并同時更新區間終點。

算出總共加入了多少區間記錄為count，

最后總數減去count.得到結果

解題代碼

?

class Solution {public int eraseOverlapIntervals(int[][] intervals) {int n = intervals.length;if(n==0){return 0;}for(int i = 0;i<n-1;i++){for(int j = 0;j<n-1-i;j++){if((intervals[j][1]>intervals[j+1][1]) ||(intervals[j][1]==intervals[j+1][1] && intervals[j][0]>intervals[j+1][0])){int[] tmp = intervals[j];intervals[j] = intervals[j+1];intervals[j+1] = tmp;}}}int count =1;int end = intervals[0][1];for(int i = 0;i<n;i++){int istart = intervals[i][0];if(istart>=end){end = intervals[i][1];count ++;}}int res= n-count;return res;} }

?解題結果

執行用時 :?516 ms, 在Non-overlapping Intervals的Java提交中擊敗了5.20%?的用戶

內存消耗 :?54.3 MB, 在Non-overlapping Intervals的Java提交中擊敗了5.05%?的用戶

總結

以上是生活随笔為你收集整理的Leetcode-435:无重叠区间的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。