学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2037

//贪心
/*
此题可以用动态规划做，也可以用贪心做。
DP做法：首先排序为排节目开始时间，
接下来就是选当前节目开始时间大于上一个节目的结束时间的最快结束的节目
贪心做法:如果排节目的结束时间，
接下来就是选当前节目的开始时间大于上一个节目的结束时间的第一个节目就可以了，
故选后者思路更快捷
*/
#include <iostream>
#include <algorithm>

using namespace std;

struct Pro {
 int beg;
 int end;
};
int cmp (const Pro a, const Pro b)
{
 return a.end < b.end;
}
int main ()
{
 Pro d[100];
 int i, j;
 int n, result;
 int preb;//前一个结束时间
 while (cin >> n && n) {
  for (i = 0; i < n; i++) {
   cin >> d[i].beg >> d[i].end;
  }
  sort (d, d+n, cmp);//以结束时间排序
  preb = d[0].end;
  result = 1;
  for (i = 1, j = 1; i < n; i = j) {
   while (j < n && preb > d[j].beg) j++;//找到满足条件的下一个节目
   if (j < n) {
    preb = d[j].end;
    result ++;
   }
  }
  cout << result << endl;
 } 
 return 0;
}