本文主要是介绍【微软算法面试高频题】区间覆盖问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

微软和谷歌的几个大佬组织了一个面试刷题群，可以加管理员VX：sxxzs3998（备注CSDN），进群参与讨论和直播

1. 问题

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

示例：
输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

2. 解析

对于这种区间问题，如果没啥头绪，首先排个序看看，比如我们按照区间的起点进行升序排序：

排序之后，两个相邻区间可能有如下三种相对位置：

按照起点升序排列，起点相同时按照终点降序排列

假设得到如下排序：

对于这三种情况：

对于情况一，找到了覆盖区间，那么让覆盖区间数+1

对于情况二和情况三，如上图，在遍历到线段2时，发现线段1与线段2相交或完全不相交则更新right=2.right，left不变仍等于1.left（left和right指遍历到此轮时的参考线段范围）。left不变是因为往后遍历时后面的线段起始点不可能比left再小了，left此时没有参考价值了，所以不用更新left。

依据几种情况，我们可以写出如下代码：

class Solution {    //区间问题
    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 left = intervals[0][0];
        int right = intervals[0][1];
​
        int res = 0;
        for(int i = 1; i < intervals.length; i++){
            // 情况一，找到覆盖区间
            if(intervals[i][0] >= left && intervals[i][1] <= right) res++; 
            // 情况二，情况三 更新right
            if((right >= intervals[i][0] && right <= intervals[i][1]) || intervals[i][0] >= right) right = intervals[i][1];
        }
        return intervals.length - res;
    }
}

微软和谷歌的几个大佬组织了一个面试刷题群，可以加管理员VX：sxxzs3998（备注CSDN），进群参与讨论和直播

这篇关于【微软算法面试高频题】区间覆盖问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！