本题的贪心算法策略需要深入思考一下

看到题目，最初没有理解题目的要求：看尽量多的完整的节目。尽量多是指数量多，自己理解成观看的时间最长。这样想其实简化了这道题。
正确理解题意后，首先想到的想法是：选择一个节目A，结束后选择另一个节目，如果节目A的时间同时覆盖了节目BC的时间，那么A就不应该看。怎么选择合适的节目？如果都把所有的节目考察一遍，统计看到的节目数量，成了穷举法，不是贪心算法。
遇到第一个关卡：如何在思维上找到突破口/切入点，当思路到达“如何选择合适的节目”这个问题时卡住，应该进一步思考“什么是合适的节目？”
这道题的贪心策略不再显而易见，像是解数学题，某个思路可以吗？需要深入思考、验证，不能蜻蜓点水之后就草率感觉“这样的思路好像不行吧”。

一个判断逻辑没有选择好浪费了大段时间

问题是这样的：
当遇到“当前节目能不能计入总数？”这个问题时，思路就绕了一小会，产生了下面的邪恶的代码。
这段代码在本地测试样例输入后，通过，到OJ上答案错误。
开始分析“样例中没有涉及但可能出现的测试数据”：如果节目A和节目B的时间完全重叠呢？详情见代码中的【错误1】
根据这个新情况修改一次后，造成【错误2】
修改错误2，造成【错误3】

感受：太着急的想法引来的问题多，复杂的想法引来的问题多。很多“直接的办法”往往是简单且可行的。
当一遇到“这个办法怎么这么复杂，要考虑的情况怎么这么多”的感觉时，你就要提高警惕了：思路上很有可能已经误入歧途。
很多时候，复杂不是问题本身困难，而是解决方法有待改进的征兆。
而误入歧途的根源是：着急，懒惰。想到一个办法就立马采用，而不进一步斟酌。

罪魁祸首：

for (former = i - 1; former > 0; former--)
{if( list[i].tag == 1 && list[former].T_e > list[i].T_s){break;}if(former == 0){num++;list[i].tag = 1;}
}
/*former是游标，依次指向前面的节目*num是可以收看的节目的总数，记录的是整个程序的最终输出结果*tag是标记某个节目是否收看过了*/

这段代码的背后的想法是：当前节目current能否计入num？取决于current的开始时间是否在前面“收看过的节目”的时间段中。于是拿着current的开始时间去和前面标记为已收看（tag==1;）的节目的时间段比较。
去和前面的时间比较！！！
一个罪恶的想法：去和前面的数据比较。
但凡是要回头在前面处理过的数据中再捯饬，都是需要谨慎谨慎再谨慎的！
就目前遇到的程序中，似乎需要回头的时候，总有一个利器可以代替回头看：用一个变量/哨兵记录一下“目前处于什么状态”。

太有用了！太好用了！

答案中的做法：

int currentTime = 0;for (int i = 0; i < n; i++){if (currentTime <= list[i].T_s){currentTime = list[i].T_e;num++;}}

无需回头看，无需tag标记。
写到这里，仔细想想，最初都想到了用tag标记是否看过某个节目，这就是向已经处理过的数据中添加tag的想法。为什么不更直接点，将“当前时间”作为tag来表示数据处理到了何处？！
功力不够，继续修炼！

完整代码

#include 
#include 
using namespace std;
struct show {int T_s;int T_e;int tag; //tag==0表示未看，tag==1表示已看//用于排序sortbool operator < (const show & B) const{return T_e < B.T_e;}
} list[105];
int totalNum[105], output = 0;
int main()
{int n;//int num = 0;int num;while (scanf("%d", &n) != EOF){if (n == 0)break;num = 0; //清除上一个测试用例的计数结果for (int i = 0; i < n; i++){scanf("%d%d", &list[i].T_s, &list[i].T_e);list[i].tag = 0;}sort(list, list + n);//list[i]为当前节目——当前结束最早的节目for (int i = 0; i < n; i++){int former;if (list[i].tag == 0){//错误2的版本：for(former = i; former > 0; former--)for (former = i - 1; former > 0; former--){//如果前面没有冲突则num++//如果前面有冲突则i++/*【错误1】/*if中添加了tag的检查，这个造成了错误：如果list[0]和list[1]完全一样则多计数一次*因为当考察list[1]时，list[1].tag==0，无法在former==1时break*当former==0时，该if满足，但是进入if后break与否都不影响former==0*break：说明时间冲突，但是此时former仍然==0，导致有冲突的情况下节目数仍要加1*不break：说明时间没有冲突，此时是正确的。*if (list[former].tag == 1 && list[former].T_e > list[i].T_s)*尝试改进：去掉list[former].tag==1这个条件，造成错误2*//*【错误2】这个if条件会导致former==i时，即节目A和节目A比较，而节目A.T_e>节目A.T_s恒成立*导致后面所有的输入都不被正确处理*改进：former的初始值从i-1开始， 导致错误3*//*【错误3】回到了原点，下面这个if中没有list[former].tag == 1的检查，会造成节目A并没有收看，*但考察节目B（i=B）时，节目B的时间与A去比较，由于A压根没有看，所以不需要与A比较！*另外一个错误：当i==0时，former==-1，导致list[0]这个第一个节目永远都无法标记为可以观看的。*问题的根源：if(former == 0) num++，这个增加可收看的节目个数的“判断条件”选的非常不好！！！*/if(list[former].T_e > list[i].T_s){break;}}if (former == 0){num++;list[i].tag = 1;}}}totalNum[output++] = num;/*这是答案中的版本，简洁明了！！！！！！！！！！！！！！！！！！*思想是：添加一个指向当前时间点的哨兵currentTime*于是，不再需要回顾（关注）前面节目的时间段了！*直接将currentTime与待考察的节目队列中下一个节目的开始时间T_s比较*currentTime<=list[i].T_s说明当前时间在下一个节目开始之前，则下一个节目可以收看！int currentTime = 0;for (int i = 0; i < n; i++){if (currentTime <= list[i].T_s){currentTime = list[i].T_e;num++;}}totalNum[output++] = num;*/}for (int i = 0; i < output; i++){printf("%d\n", totalNum[i]);}return 0;
}