题解 AT1504 【ドキドキデート大作戦高橋君】
紫题
2018-11-05 16:47:21
题意：给出m个区间，求有多少个区间能被其他区间完全覆盖
将所有区间按照左端点排序，以贪心的方法扫一遍，就能找到没有被其他区间完全覆盖的区间了
既然你能找到这题，我相信你能瞬间做出来的
$Code:$
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct w{int id,l,r;}e[100010];
bool cmp(w a,w b){return a.l<b.l;}
int a[300010],n,m,cpr,cpr_l,sum;
bool vis[100010];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&e[i].l,&e[i].r);
e[i].id=i;
}
sort(e+1,e+m+1,cmp);
cpr=1,cpr_l=e[1].l;
for(int i=2;i<=m;i++){
if(e[i].l>cpr_l) if(!vis[e[cpr].id]){sum++;vis[e[cpr].id]=1;}
if(e[i].r>e[cpr].r){
cpr_l=max(cpr_l,e[cpr].r+1);
cpr=i;
}
else cpr_l=max(cpr_l,e[i].r+1);
}
if(cpr_l<=e[cpr].r) if(!vis[e[cpr].id]){sum++;vis[e[cpr].id]=1;}
printf("%d\n",m-sum);
for(int i=1;i<=m;i++) if(!vis[i]) printf("%d\n",i);
return 0;
}
```