题意
有n个区间，要求删除一些区间使得不存在三个相交的区间。找出删除的最少区间。
分析
是个比较显然的贪心吧。
先按照区间的左起点进行排序，然后从左往右扫，当有三个区间相交的时候，删除那个右端点最远的那个区间。
这个想法显然是没错的，但是问题是n最大是50000，我们该怎么在时间复杂度以内边扫边找相交区间呢？
我们可以在从左到右扫的时候维护一个vector，里面是到目前为止，右端点最远的三个区间。我们判断相交是要从这里面判断就可以。当这里面的三个区间相交的时候，根据上面的规则删除，当不想交的时候，把新区间加进来，去掉右端点最近的一个（但是并不是删除，只是从这个vector中删除而已）。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <algorithm> 5 #include <set> 6 #include <map> 7 #include <vector> 8 #include <queue> 9 #include <stack> 10 #include <iostream> 11 #include <cmath> 12 13 using namespace std; 14 typedef long long LL; 15 typedef unsigned long long ull; 16 const int INF=2147483600; 17 const int maxn=50000+100; 18 19 struct Node{ 20 int l,r,id; 21 bool vis; 22 bool operator <(const Node &rhs)const{ 23 return l<rhs.l; 24 } 25 }node[maxn]; 26 int T,n; 27 int main(){ 28 scanf("%d",&T); 29 for(int t=1;t<=T;t++){ 30 scanf("%d",&n); 31 for(int i=1;i<=n;i++){ 32 scanf("%d%d",&node[i].l,&node[i].r); 33 node[i].id=i; 34 node[i].vis=0; 35 } 36 sort(node+1,node+1+n); 37 vector<Node>V; 38 int num; 39 vector<int>ans; 40 41 for(int i=1;i<=n;i++){ 42 //cout<<node[i].l<<" "<<node[i].r<<endl; 43 V.push_back(node[i]); 44 if(V.size()<3)continue; 45 sort(V.begin(),V.end()); 46 47 if(V[0].r>=V[1].l&&V[2].l<=V[1].r&&V[2].l<=V[0].r){ 48 int M=-1; 49 M=max(M,max(max(V[0].r,V[1].r),V[2].r)); 50 vector<Node>::iterator it; 51 for( it=V.begin();it!=V.end();it++){ 52 if(it->r==M){ 53 ans.push_back(it->id); 54 V.erase(it); 55 break; 56 } 57 } 58 } 59 if(V.size()>=3){ 60 int M=INF; 61 for(int i=0;i<3;i++){ 62 M=min(M,V[i].r); 63 } 64 vector<Node>::iterator it; 65 for(it=V.begin();it!=V.end();it++){ 66 if(it->r==M){ 67 V.erase(it); 68 break; 69 } 70 } 71 } 72 } 73 printf("%d ",ans.size()); 74 sort(ans.begin(),ans.end()); 75 for(int i=0;i<ans.size();i++){ 76 if(i!=0)printf(" "); 77 printf("%d",ans[i]); 78 } 79 if(ans.size()!=0) 80 printf(" "); 81 } 82 return 0; 83 }