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);}}