Java——無重疊區間

題目連結

leetcode線上oj題——無重疊區間

題目描述

給定一個區間的集合 intervals ，其中 intervals[i] = [starti, endi] 。傳回 需要移除區間的最小數量，使剩餘區間互不重疊 。

題目示例

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

輸出: 1

解釋: 移除 [1,3] 後，剩下的區間沒有重疊。

輸入: intervals = [ [1,2], [1,2], [1,2] ]

輸出: 2

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

輸入: intervals = [ [1,2], [2,3] ]

輸出: 0

解釋: 你不需要移除任何區間，因為它們已經是無重疊的了。

題目提示

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

解題思路

先考慮給定的區間内可以最多安排多少個無重疊的區間sum，然後用整個數組長度減去這個sum即可得到需要移除區間的最小數量

如果按照起始點和結束點之間的距離排序，從小到大，使用貪心算法盡可能的安排所有距離最短的區間

假設有[1,6][6,10][5,7]這三個區間，使用距離最小的思想顯然隻能安排[5,7]這個區間，然而最優解是[1,6][6,10]這兩個區間，是以距離最小的貪心思想是不對的

如果按照起始點排序，從小到大，使用貪心算法盡可能的安排所有起始點最小的區間

假設有[1,10][2,4][5,6]三個區間，使用起始點最小的思想顯然隻能安排[1,10]這個區間，然而最優解是[2,4][5,6]這兩個區間，是以起始點最小的貪心思想是不對的

如果按照結束點排序，從小到大，使用貪心算法盡可能的安排所有結束點最小的區間

可以發現這種思想得到的結果是正确的

是以，我們先按照結束點從小到大排序數組，然後從數組第一個元素開始周遊，如果目前元素和已經安排的元素有沖突，就通路下一個元素，否則就安排這個元素，讓sum++

最後讓intervals.length - sum即可得到答案

代碼

class Solution {
    public class compare implements Comparator<int[]>{
        @Override
        public int compare(int[] arr1, int[] arr2){
            return arr1[1] - arr2[1];
        }
    }
    
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new compare());
        int sum = 1;
        int index = 0;
        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] >= intervals[index][1]){
                sum++;
                index = i;
            }
        }
        return intervals.length - sum;
    }
}