641
WIKIOI-1214 線段覆蓋
題目描述 Description
給定x軸上的N（0<N<100）條線段，每個線段由它的二個端點a_I和b_I確定，I=1,2,……N.這些坐標都是區間（－999，999）的整數。有些線段之間會相互交疊或覆蓋。請你編寫一個程序，從給出的線段中去掉盡量少的線段，使得剩下的線段兩兩之間沒有內部公共點。所謂的內部公共點是指一個點同時屬於兩條線段且至少在其中一條線段的內部（即除去端點的部分）。
輸入描述 Input Description
輸入第一行是一個整數N。接下來有N行，每行有二個空格隔開的整數，表示一條線段的二個端點的坐標。
輸出描述 Output Description
輸出第一行是一個整數表示最多剩下的線段數。
樣例輸入 Sample Input
3
6 3
1 3
2 5
樣例輸出 Sample Output
2
數據範圍及提示 Data Size & Hint
0<N<100
//貪心算法
#include<stdio.h>
#include<algorithm>
using namespace std;
struct node
{
int a,b;
}p[200];
int swap(int &a,int &b)//交換a和b的值
{
int t;
t=a;
a=b;
b=t;
}
int cmp(node x,node y)
{
if(x.b!=y.b) return x.b<y.b;//隻能按照右端點從小到大排序（防止有多個右端點相同但左端點不同的）
}
int main()
{
int i,j,n,end,flag,sum;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d %d",&p[i].a,&p[i].b);
if(p[i].a>p[i].b)//必須要滿足前小後大，不滿足就交換
swap(p[i].a,p[i].b);
}
sort(p,p+n,cmp);//按b從小到大排序
flag=0;//先拿第一個的與後麵的比較，一旦發現沒有公共點的，更新flag（每次讓下一個數左端點的比較flag所在的右端點）
sum=1;
for(i=1;i<n;i++)
{
if(p[i].a<p[flag].b)//去掉有公共點的 （隻要左端點大於等於現在的端點就滿足！）
continue;
flag=i;//更新剩下的端點
sum++;
}
printf("%d\n",sum);
return 0;
}
最後更新：2017-04-03 12:55:32