hdoj problem 2037 今年暑假不AC(貪心（基礎題+模闆）)

今年暑假不AC

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

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 29599    Accepted Submission(s): 15651

Problem Description “今年暑假不AC？”

“是的。”

“那你幹什麼呢？”

“看世界杯呀，笨蛋！”

“@#$%^&*%...”

确實如此，世界杯來了，球迷的節日也來了，估計很多ACMer也會抛開電腦，奔向電視了。

作為球迷，一定想看盡量多的完整的比賽，當然，作為新時代的好青年，你一定還會看一些其它的節目，比如新聞聯播（永遠不要忘記關心國家大事）、非常6+7、超級女生，以及王小丫的《開心辭典》等等，假設你已經知道了所有你喜歡看的電視節目的轉播時間表，你會合理安排嗎？（目标是能看盡量多的完整節目）

Input 輸入資料包含多個測試執行個體，每個測試執行個體的第一行隻有一個整數n(n<=100)，表示你喜歡看的節目的總數，然後是n行資料，每行包括兩個資料Ti_s,Ti_e (1<=i<=n)，分别表示第i個節目的開始和結束時間，為了簡化問題，每個時間都用一個正整數表示。n=0表示輸入結束，不做處理。

Output 對于每個測試執行個體，輸出能完整看到的電視節目的個數，每個測試執行個體的輸出占一行。  

Sample Input

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0
        

Sample Output

5
        

Author lcy  

Source ACM程式設計期末考試（2006/06/07）

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

struct node

{

int start;

int end;

}t[110];

int cmp(node a,node b)

{

 if(a.start!=b.start)

   return a.end<b.end;

   if(a.end!=b.end)

     return a.start<b.start;

} 

int main()

{

  int n;

  while(scanf("%d",&n),n)

  {

  int i,max;

  for(i=1;i<=n;i++)

   scanf("%d%d",&t[i].start,&t[i].end);

   sort(t+1,t+n+1,cmp);

   max=t[1].start;

   int count=0;

   for(i=1;i<=n;i++)

     if(max<=t[i].start)//逐漸利用貪心的思想進行查找符合條件的，并且不斷更新切入點

     {

       count++;

 max=t[i].end;

}

 printf("%d\n",count);

  }

  return 0;

}