一、題目大意
標簽: 貪心
https://leetcode.cn/problems/non-overlapping-intervals
給定一個區間的集合 intervals ，其中 intervals[i] = [starti, endi] ，回傳 需要移除區間的最小數量，使剩余區間互不重疊 ，
示例 1:
輸入: intervals = [[1,2],[2,3],[3,4],[1,3]]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區間沒有重疊，
示例 2:
輸入: intervals = [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個 [1,2] 來使剩下的區間沒有重疊，
示例 3:
輸入: intervals = [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區間，因為它們已經是無重疊的了，
提示:
- 1 <= intervals.length <= 105
- intervals[i].length == 2
- -5 * 104 <= starti < endi <= 5 * 104
二、解題思路
求最小的移除區間個數，等價于盡量多保留不重疊的區間，在選擇要保留區間時，區間的結尾十分重要：選擇的區間結尾越小，余留給其它區間的空間就越大，就越能保留更多的區間，因此我們采取的貪心策略為：優先保留結尾小且不相交的區間，
具體實作方法為，先把區間按照結尾的大小進行增序排序，每次選擇結尾最小且和前一個選擇的區間不重疊的區間，
輸入陣列區間為[[1, 2], [2, 4], [1, 3]]，排序后的陣列為[[1, 2], [1, 3], [2, 4]]，按照貪心策略，首先初始化為區間[1, 2]，由于[1, 2]與[1, 3]相交，我們跳過該區間；由于[2, 4]與[1, 2]不相交，我們將其保留，因此最終保留的區間為[[1, 2], [2, 4]]，
三、解題方法
3.1 Java實作
public class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
int n = intervals.length;
// 二維陣列排序
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int removed = 0;
int prev = intervals[0][1];
for (int i = 1; i < n; i++) {
if (intervals[i][0] < prev) {
removed++;
} else {
prev = intervals[i][1];
}
}
return removed;
}
}
四、總結小記
- 2022/7/14 趕緊把wps卸載了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499347.html
標籤：其他