贪心最主要的问题就是无后效性
当前最优解就是全局最优解
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- struct act{
- int start;
- int end;
- }a[105];
- int cmp(act a,act b){
- return a.end<b.end;
- }
- int main(){
- int n;
- while(~scanf("%d",&n)){
- for(int i=1;i<=n;i++){
- cin>>a[i].start>>a[i].end;
- }
- //printf("\n");
- sort(a+1,a+n+1,cmp);
- //for(int i=1;i<=n;i++){
- // printf("%d %d\n",a[i].start,a[i].end);
- //}
- int i=1,sum=1;
- for(int j=2;j<=n;j++){
- if(a[j].start>=a[i].end){
- sum++;
- i=j;
- }
- }
- printf("%d\n",sum);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2793831.html