hdu2037今年暑假不AC 贪心
hdu2037今年暑假不AC
第一次看贪心感觉很像动态规划
。。。。。。。。。。。。
首先对n中节目排序
例如题中数据排序后为
0 7
1 3
2 9
3 4
3 8
4 14
5 10
6 12
8 18
10 15
15 19
15 20
之后就是贪心的思想了
用最少的时间看最多的节目
#include<iostream>using namespace std;struct TV{int s,e;bool flag;} S[101];bool cmp(TV a,TV b){if(a.s==b.s) return a.e<b.e;else return a.s<b.s;}main(){int n,i,end,num;while(scanf("%d",&n),n){for(i=1;i<=n;i++)scanf("%d%d",&S[i].s,&S[i].e);sort(S+1,S+n+1,cmp);num=end=0;for(i=1;i<=n;i++){if(S[i].s>=end){end=S[i].e;num++;}else{if(S[i].e<end) end=S[i].e;}}printf("%d\n",num);}}