hdu 2037 今年暑假不AC （貪心）

今年暑假不AC

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

題意:标準的貪心算法

附貪心算法 不妨用Begin[i]和End[i]表示事件i的開始時刻和結束時刻。則原題的要求就是找一個最長的序列a1 < a2 < … <

an，滿足： Begin[a1] < End[a1] < =…<= Begin[an] < End[an]

可以證明，如果在可能的事件a1 < a2 < … < an中選取在時間上不重疊的最長序列，那麼一定存在一個包含a1（結束最早）的最長序列。

方法

将所有節目的完成時間排序 由上面的分析可知 最早結束的節目一定包括在最終的選擇之内

附個代碼

#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
struct show
{
    int s;
    int e;
}pro[];
bool cmp(show a,show b)
{
    return a.e<b.e;
}
int main()
{
    while(scanf("%d",&n)!=EOF&&n)
    {
        int cnt=,i;
        memset(pro,,sizeof(pro));
        for(i=;i<n;i++)
        {
            scanf("%d%d",&pro[i].s,&pro[i].e);
        }
        sort(pro,pro+n,cmp);
        int tmp=pro[].e;
        for(i=;i<n;i++)
            {
                if(pro[i].s>=tmp)
                    {
                    cnt++;
                    tmp=pro[i].e;
                    }
            }
        printf("%d\n",cnt);
    }
    return ;
}