基础贪心算法（HDU2037今年暑假不AC）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2037

下面我附上两篇代码，一篇是AC的，另一篇是WA的，错误原因是什么谁知道麻烦告诉我，谢谢了

AC代码：

1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
4. struct Time
5. {
6. int s,e;
7. }N[101];
8. bool cmp(struct Time a,struct Time b)
9. {
10. return a.e<b.e;
11. }
12. int main()
13. {
14. int ans,t,i;
15. while(cin>>t)
16. {
17. if(t==0) break;
18. ans=1;
19. for(i=0;i<t;i++)
20. cin>>N[i].s>>N[i].e;
21. sort(N,N+t,cmp);
22. int n=N[0].e;
23. for(i=1;i<t;i++)
24. {
25. if(N[i].s>=n)
26. {
27. ans++;
28. n=N[i].e;
29. }
31. }
32. cout<<ans<<endl;
33. }
34. return 0;
35. }

WA代码：

1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
4. struct Time
5. {
6. int s,e;
7. }N[101];
8. bool cmp(struct Time a,struct Time b)
9. {
10. return a.e<b.e;
11. }
12. int main()
13. {
14. int ans,t,i;
15. while(cin>>t)
16. {
17. if(t==0) break;
18. ans=1;
19. for(i=0;i<t;i++)
20. cin>>N[i].s>>N[i].e;
21. sort(N,N+t,cmp);
22. for(i=1;i<t;i++)
23. {
24. if(N[i].s>=N[i-1].e) ans++;
25. }
26. cout<<ans<<endl;
27. }
28. return 0;
29. }

知道原因了！

1. for(i=1;i<t;i++)
2. {
3. if(N[i].s>=N[i-1].e)
4. ans++;
5. }

这样比较的只是两个相邻的区间，如果某个节目的开始时间小于上一个节目的
结束时间，但是却大于前面第二个节目的结束时间ans的值依旧不会加一！