贪心基本题， 有助于理解贪心算法的思想
#include <cstdio>
#include <algorithm>
using namespace std;
struct Program
{
int begin, end;
} programs[100];
/** 贪心： 贪心算法的基本步骤 ：
* 1、从问题的某个初始解出发。
* 2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。
* 3、将所有部分解综合起来，得到问题的最终解。 */
/* * 首先把每个节目的数据都存起来，开始时间和结束时间，然后按照开始时间来排序，
* 这里貌似可以不用二级排序，单单对开始时间排序就行了。
* 运用贪心： 要在所有节目中找出能够看到的完整的（也就是区间不重合）节目，
* 就可以想成分成各个小部分解，用for循环从begin时间小的开始算起，
* 设定一个边界值bound存你已经选好要看的节目的结束时间，再用结束时间和下一个节目的开始时间对比，
* 如果bound < next_program的begin 则 sum + 1，如果bound > next_program的begin，再对比bound和next_program的end，把较小的赋给bound，
* 相当于替换了之前那个节目(虽然已经++了)，因为新节目的结束时间更早！
* 具体算法在下面的for里. */
int cmp(const Program &a, const Program &b) //按开始时间升序排列，如果开始时间相同则先结束的在前
{
if(a.begin == b.begin)
return a.end < b.end;
else
return a.begin < b.begin;
}
int main()
{
int n, i;
while(scanf("%d", &n), n)
{
for(i = 0; i < n; i ++)
scanf("%d%d", &programs[i].begin, &programs[i].end);
sort(programs, programs + n, cmp);
int bound, sum = 1;
bound = programs[0].end;
for(i = 1; i < n; i ++)
{ /* 贪心！ */
if(bound <= programs[i].begin)
{
sum ++;
bound = programs[i].end;
}
else if(programs[i].end < bound)
{
bound = programs[i].end;
}
}
printf("%d\n", sum);
}
return 0;
}