1615: 找区间
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 291 Solved: 122
[Submit][Status][Web Board]Description
在X轴上有n个闭区间，去掉尽可能少的区间使剩下的区间都不相交
Input
多组测试数据
第一行输入n（n<=1000）
接下来n行每行两个数a,b代表闭区间的两个端点。
（a,b<=1000000）
Output
输出最小的删除的区间数
Sample Input
3
10 20
15 10
20 15
Sample Output
2
【分析】贪心算法--选择不相交区间问题
【思路】首先按照区间的结束位置升序排序，一次考虑各个区间。如果没有和已经选择的区间冲突就选。
【代码】
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e3+5;
struct node{int l,r;
}a[maxn];
bool cmp(node x,node y)
{return x.r<y.r;
}
int main()
{int n;while(~scanf("%d",&n)){for(int i=0;i<n;i++){int x,y;scanf("%d%d",&x,&y);if(x>y)swap(x,y);a[i].l=x,a[i].r=y;} sort(a,a+n,cmp);// for(int i=0;i<n;i++)cout<<a[i].l<<","<<a[i].r<<endl;int cnt=1,t=a[0].r;for(int i=1;i<n;i++){if(a[i].l>t){cnt++;t=a[i].r;}}cout<<n-cnt<<endl;}
}