方法一:枚举
对于列表中的每个区间 p,我们可以枚举其余的所有区间,并依次判断区间 p 是否被某个区间所覆盖。
int n = inte.size();
int ans = n;
for (int i = 0; i < inte.size(); ++i) {
for (int j = 0; j < inte.size(); ++j) {
if (i != j && inte[j][0] <= inte[i][0] && inte[i][1] <= inte[j][1]) {
--ans;
break;
}
}
}
方法二:排序 + 遍历
我们首先假设所有区间的左端点都不相同。以左端点递增排序,那么到端点i时,i之前的线段都不可能被删除,因为i之前的左端点都比i小,只有当i的右端点小于上一个线段的右端点时,i会被删除。
当左端点可能相同时,再以右端点递减排序,这样仍可以保持i之前的线段不可能删除的性质。这样就可以解决问题了。
重点:利用排序构造出一种保证i之前的线段不可能被删除的特点。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(vector<int> &a,vector<int> &b){
return a[0]<b[0] || (a[0]==b[0] && a[1]>b[1]);
}
int removeline(vector<vector<int> > &inte){
int n=inte.size();
int ans=n;
sort(inte.begin(),inte.end(),cmp);
int rmax=inte[0][1];
for(int i=1;i<n;i++){
if(inte[i][1]<=rmax){
--ans;
}
else rmax=inte[i][1];
}
return ans;
}
int main(){
vector<vector<int> > inte;
int n;scanf("%d",&n);
for(int i=0;i<n;i++){
vector<int> v;
int a1,a2;
scanf("%d%d",&a1,&a2);
v.push_back(a1);
v.push_back(a2);
inte.push_back(v);
}
int ans=removeline(inte);
printf("%d\n",ans);
return 0;
}
力扣版本
class Solution {
public:
int removeCoveredIntervals(vector<vector<int>>& intervals) {
int n = intervals.size();
sort(intervals.begin(), intervals.end(), [](const vector<int>& u, const vector<int>& v) {
return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
});
int ans = n;
int rmax = intervals[0][1];
for (int i = 1; i < n; ++i) {
if (intervals[i][1] <= rmax) {
--ans;
}
else {
rmax = intervals[i][1];
}
}
return ans;
}
};