nyoj891(區間上的貪心)

nyoj891(區間上的貪心)

題目意思：

給一些閉區間，求最少需要多少點，使得每個區間至少一個點。

樣例輸入

4
1 5
2 4
1 4
2 3
3
1 2
3 4
5 6
1
2 2

樣例輸出

1
3
1

題目分體：

 

區間貪心，我認為區間上的貪心算法，最主要的還是排序的方式，只要排序的方式合理，就能很好的使用貪心，貪心的本質雖然是選擇當前最優的解，作為全軍最優解的一部分，如果排序不當回造成好的條件選擇。本題只給出的排序的方式，相信大家都會使用貪心的。

 

AC代碼：

#include
#include
using namespace std;
struct node{
int r,l;
}a[101];
int cmp(node a1,node b1){//按右端點從大到小，左端點從大到小定義排序方式。
if(a1.r else if(a1.r==b1.r&&a1.l>b1.l) return 1;
return 0;
}
int main()
{
int n;
while(cin>>n){
int x,y;
for(int i=0;i cin>>x>>y;
a[i].l=x a[i].r=x>y?x:y;
}
sort(a,a+n,cmp);
int k=1;
node p=a[0];
for(int i=1;i if(p.r p=a[i]; k++;
}
}
cout< }
return 0;
}