嘉兴网站推广优化费用,增城市网站建设,网店代运营违法吗,驰业网站建设删除被覆盖区间 题目描述贪心法代码演示 题目描述 难度 - 中等 leetcode1288. 删除被覆盖区间 给你一个区间列表#xff0c;请你删除列表中被其他区间所覆盖的区间。 只有当 c a 且 b d 时#xff0c;我们才认为区间 [a,b) 被区间 [c,d) 覆盖。 在完成所有删除操作… 删除被覆盖区间 题目描述贪心法代码演示 题目描述 难度 - 中等 leetcode1288. 删除被覆盖区间 给你一个区间列表请你删除列表中被其他区间所覆盖的区间。 只有当 c a 且 b d 时我们才认为区间 [a,b) 被区间 [c,d) 覆盖。 在完成所有删除操作后请你返回列表中剩余区间的数目。 示例 输入intervals [[1,4],[3,6],[2,8]] 输出2 解释区间 [3,6] 被区间 [2,8] 覆盖所以它被删除了。 提示 1 intervals.length 1000 0 intervals[i][0] intervals[i][1] 10^5 对于所有的 i ! jintervals[i] ! intervals[j] 贪心法 所谓区间问题就是线段问题让你合并所有线段、找出线段的交集等等。主要有两个技巧 1、排序。常见的排序方法就是按照区间起点排序或者先按照起点升序排序若起点相同则按照终点降序排序。当然如果你非要按照终点排序无非对称操作本质都是一样的。 2、画图。就是说不要偷懒勤动手两个区间的相对位置到底有几种可能不同的相对位置我们的代码应该怎么去处理。 关于本题 对于这种区间问题如果没啥头绪首先排个序看看比如我们按照区间的起点进行升序排序 排序之后两个相邻区间可能有如下三种相对位置 对于这三种情况我们应该这样处理 对于情况一找到了覆盖区间。
对于情况二两个区间可以合并成一个大区间。
对于情况三两个区间完全不相交。
代码演示 /*** 去除覆盖的线段* param intervals* return*/public int removeCoveredIntervals(int[][] intervals) {//起点升序终点降序Arrays.sort(intervals,(a,b) - {if(a[0] b[0]){return b[1] - a[1];}return a[0] - b[0];});//记录被覆盖的线段数int res 0;int left intervals[0][0];int right intervals[0][1];for (int i 1; i intervals.length;i){//情况一 找到覆盖区间if (left intervals[i][0] right intervals[i][1]){res;}//情况二 找到相交区间合并if (right intervals[i][0] right intervals[i][1]){right intervals[i][1];}//情况三 完全不相交if (right intervals[i][0]){left intervals[i][0];right intervals[i][1];}}return intervals.length - res;}
