（js）leetcode 1288. 删除被覆盖区间

小咪咪 2022-11-07 11:38 112阅读 0赞

### 题目： ###

> 给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
> 
> 只有当 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 != j：intervals\[i\] != intervals\[j\]

### 思路： ###

> 1.  按起点升序排序，起点相同时降序排序
> 
> 2. 排序之后，两个相邻区间可能有如下三种相对位置：
> 
> 情况1：找到覆盖区间
> 
> 情况2：找到相交区间，合并
> 
> 情况3：完全不相交，更新起点和终点

### 代码实现： ###

/**
     * @param {number[][]} intervals
     * @return {number}
     */
    var removeCoveredIntervals = function(intervals) {
        // 按起点升序排序，起点相同时降序排序
        intervals.sort((a,b)=>{
            if(a[0]=== b[0]) {
                return b[1]-a[1];
            }
            return a[0]-b[0];
        })
    
        // 记录合并区间的起点和终点
        let left = intervals[0][0];
        let right = intervals[0][1];
    
        let res = 0;
        for(let i = 0; i < intervals.length; i++) {
            let intv = intervals[i];
            // 情况1：找到覆盖区间
            if(left <= intv[0] && right >= intv[1]) {
                res++;
            }
            // 情况2：找到相交区间，合并
            if(right >= intv[0] && right <= intv[1]) {
                right = intv[1];
            }
            // 情况3：完全不相交，更新起点和终点
            if(right < intv[0]) {
                left = intv[0];
                right = intv[1];
            }
        }
    
        return intervals.length - res + 1;
    };

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70]: /images/20221023/88adf495d0744932b1b7e44e535edb77.png