一个方法解决三道区间问题
培养框架思维，真正爱上算法！关注公众号查看更新文章👆
相关推荐：
读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：
经常有读者问区间相关的问题，今天写一篇文章，秒杀三道区间相关的问题。
所谓区间问题，就是线段问题，让你合并所有线段、找出线段的交集等等。主要有两个技巧：
1、排序。常见的排序方法就是按照区间起点排序，或者先按照起点升序排序，若起点相同，则按照终点降序排序。当然，如果你非要按照终点排序，无非对称操作，本质都是一样的。
2、画图。就是说不要偷懒，勤动手，两个区间的相对位置到底有几种可能，不同的相对位置我们的代码应该怎么去处理。
废话不多说，下面我们来做题。
这是力扣第 1288 题，看下题目：
题目问我们，去除被覆盖区间之后，还剩下多少区间，那么我们可以先算一算，被覆盖区间有多少个，然后和总数相减就是剩余区间数。
对于这种区间问题，如果没啥头绪，首先排个序看看，比如我们按照区间的起点进行升序排序：
排序之后，两个相邻区间可能有如下三种相对位置：
对于这三种情况，我们应该这样处理：
对于情况一，找到了覆盖区间。
对于情况二，两个区间可以合并，成一个大区间。
对于情况三，两个区间完全不相交。
依据几种情况，我们可以写出如下代码：
int removeCoveredIntervals(int[][] intvs) {// 按照起点升序排列，起点相同时降序排列Arrays.sort(intvs, (a, b) -> {if (a[0] == b[0]) {return b[1] - a[1];}return a[0] - b[0];});// 记录合并区间的起点和终点int left = intvs[0][0];int right = intvs[0][1];int res = 0;for (int i = 1; i < intvs.length; i++) {int[] intv = intvs[i];// 情况一，找到覆盖区间if (left <= intv[0] && right >= intv[1]) {res++;}// 情况二，找到相交区间，合并if (right >= intv[0] && right <= intv[1]) {right = intv[1];}// 情况三，完全不相交，更新起点和终点if (right < intv[0]) {left = intv[0];right = intv[1];}}return intvs.length - res;}
以上就是本题的解法代码，起点升序排列，终点降序排列的目的是防止如下情况：
对于这两个起点相同的区间，我们需要保证长的那个区间在上面（按照终点降序），这样才会被判定为覆盖，否则会被错误地判定为相交，少算一个覆盖区间。
＿＿＿＿＿＿＿＿＿＿＿＿＿
本文只能在 labuladong 公众号查看，关注后可直接搜索本站内容：
Last updated 40 minutes ago