天天看點

hdu2037

**

求能看到的最多的頻道數

**

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

Sample Output

5

#include<stdio.h>
int main()
{
	int a[100][2];
	int n,i,j,num,temp;
	while(scanf("%d",&n),n!=0)
	{
		for(i=0;i<n;i++)
			scanf("%d%d",&a[i][0],&a[i][1]);
		for(i=0;i<n;i++)  //思路:選擇排序,對所有的結束時間進行排序
		{
			for(j=i+1;j<n-1;j++)
			{
				if(a[j][1]<a[i][1])
				{
					temp=a[i][0],a[i][0]=a[j][0],a[j][0]=temp;
					temp=a[i][1],a[i][1]=a[j][1],a[j][1]=temp;
				}
			}
		}
		num=1;  //思路:第一個節目節目肯定是可以看完的,而且它的結束時間是最早的
		temp=a[0][1];
		for(i=1;i<n;i++)
		{
			if(a[i][0]>=temp)  //思路:當節目的起始時間小于上個節目的結束時間時,那它也是可以看完整的
			{
				num++;
				temp=a[i][1];  //注意:記得把該節目的結束時間賦予temp
			}
		}
		printf("%d\n",num);
		}
	return 0;
}

           
上一篇: hdu2000
下一篇: hdu2009