题目

为了方便阅读，这里再把题目重复一遍

题目描述

暑假到了，小明终于可以开心的看电视了，但是小明喜欢的节目太多了，他希望尽量多的看到完整的节目，现在他把他喜欢的电视节目的转播时间表给你，你能帮他合理安排吗？

输入

每组输入的第一行是一个整数n（n<=100），表示小明喜欢的节目的总数。
接下来n行，每行输入两个整数si和ei（1<=i<=n），表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。

输出

输出能完整看到的电视节目的个数。

样例输入

样例输出

过程剖析

1.创建链表——输入节目信息

首先定义合适的结构体类型 Time来储存单个节目信息和 List来储存链表信息，具体如下

typedef struct time{
	int start;
	int end;
	struct time *next;
}Time;//存放电视节目时间
typedef struct list{
	Time *head;
	Time *tail;
}List; //储存链表信息

用一个结构体单独存放链表信息的目的，在于更好的归纳各个链表，在这个例子中具体体现的作用，是在建立链表时能更方便地使用尾接法。

接着定义了一个add函数，将每一次输入的信息即时地生成结点并尾接链表，函数如下：

void add(List *list,int a,int b){
	Time *p=NULL;//工具指针 暂时存放结点
	//生成新结点
	p=(Time *)malloc(sizeof(Time));
	p->start = a;
	p->end = b; 
	p->next = NULL;
	//将新结点插尾
	if(list->tail ){
		//如果链表不空，接尾
		list->tail ->next=p;
		list->tail =p;
	}else{
	//如果为空链表，令头指针指向头结点，尾指针也要指向头结点，不然，尾和头断连 
		list->head =p;
		list->tail =p;
	}

2.链表排序——以节目结束时间排序

同样定义了一个函数来进行排序，这个函数的排序思路与选择排序类似，在排序时只交换结点的数据域而不改变指针域，函数如下：

void sort(List *list,int n){//传入链表及电视节目个数 
	int i=0,start,end;//start和end 是交换工具，i控制循环次数
	Time *p1=list->head ;
	Time *p2=p1->next ;
	for(i=0;i<n;i++){
		for(p2=p1->next ;p2!=NULL;p2=p2->next){
			if(p1->end >p2->end ){
				//swap start
				start=p1->start ;
				p1->start =p2->start ;
				p2->start =start;
				
				//swap end
				end=p1->end ;
				p1->end =p2->end ;
				p2->end =end;
			}
		}
		p1=p1->next ;//p1后移 
	}
}

在不清楚结点个数（如n）时，也可通过判断p1是否为空结束循环

3.遍历链表——查询所看节目个数

又是一个函数，传入要查询的链表信息，传出所看节目数，具体如下：

int find(List *list){
	int count=1,really_end;
	Time *p=list->head ; 
	really_end=p->end ;
	while(p!=NULL){
		if(really_end<=p->start ){
			count++;
			really_end=p->end ;
		}
		p=p->next ;
	}
	return count;
}

完整main函数

int main(void){
	int n=0,i=0,count=0;
	int start=0,end=0;//临时储存开始结束时间
	int really_end=0;
	Time *p=NULL,*q=NULL;//用于遍历链表看电视 
	
	//创建空链表
	List list;
	list.head=list.tail =NULL;
	 
	scanf("%d",&n);
	
	//输入节目信息 
	for(i=0;i<n;i++){
		scanf("%d %d",&start,&end);
		add(&list,start,end);
	}
	
	//给节目排序
	sort(&list,n);
	p=list.head ;

	//遍历链表计数并输出
	count=find(&list);
	printf("%d",count); 
	 
	return 0;
}