一、题目
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
https://leetcode-cn.com/problems/non-overlapping-intervals/
二、解题思路
整体思路
区间调度问题的特点：
给出很多形如[start, end]的闭区间，算出这些区间中最多有几个互不相交的区间。
本质是求最大不相交子集。
参考https://www.jianshu.com/p/46628652f533
关键问题
1、找到最多不会重叠的区间
2、（全部区间个数）-（最多不会重叠区间个数）=（最小移除区间个数）
三、题解
暴力解法、动态规划解法
https://leetcode-cn.com/problems/non-overlapping-intervals/solution/wu-zhong-die-qu-jian-by-leetcode/
题解1: 区间调度
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;
}
}
