J - 今年暑假不AC

        这个题主要是考察贪心算法,如何能在有限时间内看最多的电视节目。解题思路是按照节目的结束时间从小到大的的顺序把节目排列一下,然后先看最先结束的节目,看完后看下一个结束时间点内有没有开始时间是可以接在当前节目后面的,如果有,将下个节目的结束时间赋给当前的结束时间,这样就算是看完了下个节目,以此类推。


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



下面是我的代码,主要是把节目的开始时间和结束时间实例化一个节目对象,然后排序,最后判断输出,值得注意的一点是自己写了快排函数,效率没有内置的sort效率高, 然后自己写了一个测试类,用来测试程序,感觉挺不错的,从Django里面的TestCase借鉴过来的。


#include <iostream>
using namespace std;
class Time
{
public:
    int tBegin;
    int tEnd;
    Time(int tb=0, int te=0):tBegin(tb), tEnd(te){}
};
const int maxn=100+1;
int n, tn;
Time time[maxn];
void Init()
{
    ///初始化输入时间表
    int ta, tb;
    for(int i=1;i<=n;i++){cin>>ta>>tb;time[i]=Time(ta, tb);}
}
void Sort(int left, int right)
{
    ///数组快速排序
    int i, j;
    Time ttime, xtemp;
    if(left>right)return;
    xtemp=time[left];
    i=left;
    j=right;
    while(i!=j)
    {
        while(time[j].tEnd>=xtemp.tEnd && i<j)j--;  //先从右边找,这非常重要
        while(time[i].tEnd<=xtemp.tEnd && i<j)i++;
        if(i<j){ttime=time[i];time[i]=time[j];time[j]=ttime;}
    }
    time[left]=time[i];
    time[i]=xtemp;
    Sort(left, i-1);
    Sort(i+1, right);
    return;
}
void Print()
{
    ///判断后输出
    int ans=0;
    int cur=0;
    for(int pi=1;pi<=n;pi++){if(time[pi].tBegin>=cur){ans++;cur=time[pi].tEnd;}}
    cout<<ans<<endl;
}
class TestCase
{
public:
    void TestSort();
};
void TestCase::TestSort()
{
    ///测试快排的函数
    for(int ti=1;ti<=n;ti++)cout<<"<"<<time[ti].tBegin<<","<<time[ti].tEnd<<">"<<endl;
}
int main()
{
    while(cin>>n && n)
    {
        //TestCase test;
        Init();
        //test.TestSort();
        Sort(1, n);
        //test.TestSort();
        Print();
    }
    return 0;
}