LeetCode 5127. 删除被覆盖区间 Remove Covered Intervals

地址 https://leetcode-cn.com/contest/biweekly-contest-15/problems/remove-covered-intervals/

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

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

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

示例：

输入：intervals = [[,],[,],[,]]

输出：

解释：区间 [,] 被区间 [,] 覆盖，所以它被删除了。

提示：

 <= intervals.length <=

 <= intervals[i][] < intervals[i][] <= ^

对于所有的 i != j：intervals[i] != intervals[j]

算法1
还是逐个比较各个区间只是被包含的区间直接填充不可能数字避免进行数组删减移动浪费时间

 class Solution {

 public:

     bool Check( vector<vector<int>>&  v,int a,int b){

         if(v[a][] == - || v[a][] == - || v[b][]==- || v[b][] == -){

             return false;

         }

         if(v[a][] <= v[b][] && v[b][] <= v[a][]){

             //a 覆盖b

             v[b][] = -; v[b][] = -;

             return true;

         }

         return false;

     }

     int removeCoveredIntervals(vector<vector<int>>& intervals) {

         if(intervals.empty()) return ;

         int count = ;

         for(int i = ; i < intervals.size()-;i++){

             for(int j =i+;j <intervals.size();j++){

                 if(Check(intervals,i,j)){

                     count++;

                 }else if(Check(intervals,j,i)){

                     count++;

                     //当前的选择已经优化掉了直接break

                     break;

                 }

             }

         }

         return intervals.size()-count;

     }

 };

巴特西

LeetCode 5127. 删除被覆盖区间 Remove Covered Intervals

最新文章

热门文章