今年暑假不AC
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10182 Accepted Submission(s): 5254
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
#include<stdio.h>
#include<stdlib.h>
struct node{
int s ;
int e ;
};
node T[105] ;
int cmp( const void *a , const void *b )
{
return (*( node *)a).e - (*( node *)b).e ;
}
int n ;
int main( )
{
while( scanf("%d" , &n ) , n )
{
for( int i = 0 ; i < n ; i++ )
scanf("%d%d" , &T[i].s , &T[i].e ) ;
qsort( T , n , sizeof( T[0] ) , cmp ) ;
int count = 1 ;
int r = T[0].e ;
for( int i = 1 ; i < n ; i++ )
{
if( T[i].s >= r )
{ r = T[i].e; count++ ;}
}
printf("%d\n" , count ) ;
}
// system( "pause" );
return 0;
}