435. 无重叠区间
我认为区间类的题型，大多数考验的是思维能力，以及编码能力，该类题型本身并无什么算法可言，主要是思维逻辑，比如本题实际上你只需要能够总结出重叠与不重叠的含义，再加上一点编码技巧，便可完成。
解题思路
正如前面所说，那么解题的关键思路就在于找到重叠区间的特性即可，我们不妨先按照start进行一次排序，再进行观察，比如数组：[[1,2],[2,3],[3,4],[1,3]]，排序后为：[[1,2],[1,3],[2,3],[3,4]]，通过观察我们很容易发现，如果前一个数组的end大于下一个数组的start，则这两个数组一定发生了重叠，这个比较容易理解，如图所示：分别有两个数组[1,2]和[1,3]
重叠部分一眼可见，但关键在于产生重叠后，应该留下谁？舍弃谁？我们不妨还是画图理解，按照题目示例，接下来一组数字是[2,3]
我们可以分开讨论，假设我们选择保留[1,3]，那么很明显下一组[2,3]将变为重叠部分。
而如果我们选择保留[1,2]，则不会再产生重叠部分。
根据题目要求，需要我们通过移除最少的区间数量来实现区间互不重叠，因此应当使用第二种方案，从原理上来说，就是当两个区间产生重叠后，我们应当保留区间范围更小的一组，因为这样更有可能避免与后面的区间再产生重叠（很容易理解的一点概念：区间范围越大，越容易发生重叠）
结论，假设有
[[s1, e1], [s2, e2], [s3, e3] ... [sn, en]]，如果e1 > s2，则将触发[s1 ,e1],[s2, e2]合并，合并规则为：如果e1 > e2，合并为[s1, e2]，否则合并为[s1, e1]，如果e1 <= s2，则无需合并，直接检查下一个区间即可。
代码实现
public int eraseOverlapIntervals(int[][] intervals) {
// 不要忘了，先按start进行排序
Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
int ans = 0;
int end = intervals[0][1];
for(int i = 1; i < intervals.length; i++){
int start = intervals[i][0];
if(end > start){
end = Math.min(end, intervals[i][1]);
ans++;
}else{
end = intervals[i][1];
}
}
return ans;
}
56. 合并区间
解题思路
本题与上一题比较相似，都是处理重叠区间的问题，我们同样可以画图理解，以题目示例1为例：[[1,3],[2,6],[8,10],[15,18]]。
首先与前一题一样，如果前一个数组的end大于下一个数组的start，则表示一定出现了重叠，而关于end部分的去留，则正好与前一题相反，前一题保留的是较小部分，本题则需要保留较大部分。
结论，假设有
[[s1, e1], [s2, e2], [s3, e3] ... [sn, en]]，如果e1 >= s2，则将触发[s1 ,e1],[s2, e2]合并，合并规则为：如果e1 > e2，合并为[s1, e1]，否则合并为[s1, e2]，如果e1 < s2，则无需合并，直接检查下一个区间即可。
代码实现
由于本题需要在原数组上进行修改，因此先借用一个list辅助记录，实际处理逻辑并没区别。
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
List<int[]> list = new ArrayList<>();
list.add(new int[]{intervals[0][0], intervals[0][1]});
for(int i = 1; i < intervals.length; i++){
int start = intervals[i][0];
int end = intervals[i][1];
if(list.get(list.size()-1)[1] < start){
list.add(new int[]{start, end});
}else{
list.get(list.size()-1)[1] = Math.max(end, list.get(list.size()-1)[1]);
}
}
return list.toArray(new int[list.size()][]);
}
}
1288. 删除被覆盖区间
解题思路
前面两题处理的都是数据范围重叠的问题，本题要解决的则是数据范围覆盖问题，我们先要搞清楚符合覆盖的条件有哪些？很明显，当s1 <= s2 且 e2 <= e1时，则认为[s2, e2]区间被[s1, e1]区间覆盖。
如下图所示：
结论，假设有
[[s1, e1], [s2, e2], [s3, e3] ... [sn, en]]，当s1 <= s2 且 e2 <= e1时，则可删除区间[s2, e2]，这里需要注意的是，为了方便处理，我们可以让start按照升序排序的同时，并让end按照降序排序，这样代码实现时只要满足e1 >= e2即可认为被覆盖了。实际上就是为了方便进行判断s1 <= s2 且 e2 <= e1
代码实现
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
Arrays.sort(intervals, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
int cnt = 0;
int preEnd = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
int curEnd = intervals[i][1];
if (preEnd >= curEnd) {
cnt++;
} else {
preEnd = curEnd;
}
}
return intervals.length - cnt;
}
}
