zcmu 1615: 找区间

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

解题报考：这是道贪心算法题，是活动安排问题的变形。

code：

<span style="font-size:18px;">#include<iostream> #include<algorithm> #include<stdio.h> #include<queue> #include<math.h> #include<string.h> #include<stdlib.h> using namespace std; typedef long long ll; struct node{ int a,b; }aa[1005]; bool cmp(node a,node b){ return a.b<b.b; } int main(){ // freopen("input.txt","r",stdin); int n; while(~scanf("%d",&n)){ int a,b; for(int i=0;i<n;i++){ scanf("%d%d",&a,&b); if(a>b){ int t=a; a=b; b=t; } aa[i].a=a; aa[i].b=b; } sort(aa,aa+n,cmp); //以右区间值从小到大排序； int j=0,num=1; for(int i=1;i<n;i++){ if(aa[i].a>aa[j].b){ num++; j=i; } } printf("%d\n",n-num); } return 0; } </span>