22-題目1434：今年暑假不AC

http://ac.jobdu.com/problem.php?pid=1434

題目描述：

“今年暑假不AC？”“是的。”“那你幹什麼呢？”“看世界杯呀，笨蛋！”“@#$%^&*%...”确實如此，世界杯來了，球迷的節日也來了，估計很多ACMer也會抛開電腦，奔向電視作為球迷，一定想看盡量多的完整的比賽，當然，作為新時代的好青年，你一定還會看一些其它的節目，比如新聞聯播（永遠不要忘記關心國家大事）、非常6+7、超級女生，以及王小丫的《開心辭典》等等，假設你已經知道了所有你喜歡看的電視節目的轉播時間表，你會合理安排嗎？（目标是能看盡量多的完整節目）

輸入：

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

輸出：

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

貪心算法，這題我不會，看了别人的，再自己寫的

#include<stdio.h>
#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>
using namespace std;

typedef struct Tvshow
{
	int begin;
	int end;
}Tvshow;
bool cmp(Tvshow a, Tvshow b)
{
	return a.end < b.end;    //按電視節目結束時間遞增排序
}

int main()
{
	int n, i, j;
	//ifstream cin("data.txt");
	while (cin >> n && n != 0)
	{
		int sum = 0, temp = 0, FinalTime = 0;
		Tvshow *tvshow = new Tvshow[n];

		for (i = 0; i < n; i++)
			cin >> tvshow[i].begin >> tvshow[i].end;
		sort(tvshow, tvshow + n, cmp);
		FinalTime = tvshow[n - 1].end;  //獲得最後一個節目的結束時間,從0開始，一共FinalTime+1個時間點
		int *Max = new int[FinalTime + 1];
		for (i = 0; i <= FinalTime; i++)
			Max[i] = 0;
		for (i = 0; i < n; i++)
		{
			temp = max(Max[tvshow[i].begin] + 1, Max[tvshow[i].end]);
			for (j = tvshow[i].end; j <= FinalTime; j++)
				Max[j] = temp;
		}
		cout << Max[FinalTime] << endl;
	}//end of while
	//system("pause");
	return 0;
}