一、題目
給定一個區(qū)間的集合蜗帜，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊耙蔑。
注意:
可以認為區(qū)間的終點總是大于它的起點摹迷。
區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”疟赊，但沒有相互重疊。
示例 1:
輸入: [ [1,2], [2,3], [3,4], [1,3] ]
輸出: 1
解釋: 移除 [1,3] 后峡碉，剩下的區(qū)間沒有重疊近哟。
https://leetcode-cn.com/problems/non-overlapping-intervals/
二、解題思路
整體思路
區(qū)間調(diào)度問題的特點：
給出很多形如[start, end]的閉區(qū)間鲫寄，算出這些區(qū)間中最多有幾個互不相交的區(qū)間吉执。
本質(zhì)是求最大不相交子集。
參考http://www.reibang.com/p/46628652f533
關(guān)鍵問題
1地来、找到最多不會重疊的區(qū)間
2戳玫、（全部區(qū)間個數(shù)）-（最多不會重疊區(qū)間個數(shù)）=（最小移除區(qū)間個數(shù)）
三、題解
暴力解法未斑、動態(tài)規(guī)劃解法
https://leetcode-cn.com/problems/non-overlapping-intervals/solution/wu-zhong-die-qu-jian-by-leetcode/
題解1: 區(qū)間調(diào)度
Java題解
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
int n = intervals.length;
if (n == 0){
return 0;
}
return n - helper(intervals);
}
private int helper(int[][] intervals){
Arrays.sort(intervals, new Comparator<int[]>(){
public int compare(int[] a, int[] b){
return a[1] - b[1];
}
});
int x_end = intervals[0][1];
int count = 1, start = 0;
for (int[] invs : intervals){
start = invs[0];
if (start >= x_end){
count++;
x_end = invs[1];
}
}
return count;
}
}
參考
1咕宿、區(qū)間調(diào)度知識點講解https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/tan-xin-suan-fa-zhi-qu-jian-tiao-du-wen-ti
