題目
給定一個區間的集合，找到需要移除區間的最小數量，使剩余區間互不重疊，
注意:
- 可以認為區間的終點總是大于它的起點，
- 區間 [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
解釋: 你不需要移除任何區間，因為它們已經是無重疊的了，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/non-overlapping-intervals
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
題解
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
// 長度為0則沒有包含關系
if (intervals.length == 0)
return 0;
// 進行排序，依靠區間大小排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// 記錄區間尾部的位置
int end = intervals[0][1];
// 需要移除的數量
int count = 0;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < end) {
//如果重疊了，必須要移除一個，所以count要加1，
//然后更新尾部的位置，我們取尾部比較小的
end = Math.min(end, intervals[i][1]);
count++;
} else {
//如果沒有重疊，就不需要移除，只需要更新尾部的位置即可
end = intervals[i][1];
}
}
return count;
}
}
1ms 38.1MB
思路如注釋，即為判斷最大區間，如果最大區間之中有結尾比它小的，則一定包含
更多題解點擊此處
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/243348.html
標籤：其他