廊坊网站建设企业,推广线上渠道,给一个免费的网站,百度收录需要多久难度#xff1a;Medium
题目#xff1a; 给你一个区间列表#xff0c;请你删除列表中被其他区间所覆盖的区间。 只有当 c a 且 b d 时#xff0c;我们才认为区间 [a,b) 被区间 [c,d) 覆盖。 在完成所有删除操作后#xff0c;请你返回列表中剩余区间的数目。 示…难度Medium
题目 给你一个区间列表请你删除列表中被其他区间所覆盖的区间。 只有当 c a 且 b d 时我们才认为区间 [a,b) 被区间 [c,d) 覆盖。 在完成所有删除操作后请你返回列表中剩余区间的数目。 示例
输入intervals [[1,4],[3,6],[2,8]]
输出2
解释区间 [3,6] 被区间 [2,8] 覆盖所以它被删除了。提示
1 intervals.length 10000 intervals[i][0] intervals[i][1] 10^5对于所有的 i ! jintervals[i] ! intervals[j]
Related Topics
数组排序 重点解题思路 明确解题思路 此题类似LeetCode[56]合并区间这道题前一道题是要将相交的区间合并但是这一道题要求将包含的区间删除这一道题明显比前一道题简单因为此题并不需要考虑交集的情况之需要考虑什么条件包含即可。 源码讲解 class Solution {public int removeCoveredIntervals(int[][] intervals) {Arrays.sort(intervals, new Comparatorint[]() {Overridepublic int compare(int[] o1, int[] o2) {return o1[0] o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]; //如果左区间相同那么就根据右区间降序排序。否则就正常根据左区间升序排序}});int cnt0,end0,pre_end0; //end是此时的右区间pre_end是上一个右区间for (int[] interval : intervals) {endinterval[1]; //拿到每次的右区间if (endpre_end){ //当此时的右区间比上一个右区间大时才能确定这两个区间并不是包含关系cnt; //既然不是包含关系 说明不用删除 数组长度可以加1pre_endend;}}return cnt;}} 运行结果 如果您还有什么疑问或解答有问题可在下方评论我会及时回复。
系列持续更新中点个订阅吧喜欢练习算法那就点个攒吧
