区间    Problem description 现给定n个闭区间[ai, bi]，1<=i<=n。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间[a, b]和[c, d]是按照升序排列的的，那么我们有a<=b 请写一个程序：读入这些区间；计算满足给定条件的不相交闭区间；把这些区间按照升序输出.  Input 第一行包含一个整数n，3<=n<=50000，为区间的数目。以下n行为对区间的描述，第i行为对第i个区间的描述，为两个整数1<=ai<=bi<=1000000，表示一个区间[ai, bi]。  Output 你应该输出计算出来的不相交的区间。每一行都是对一个区间的描述，包括两个用空格分开的整数，为区间的上下界。你应该把区间按照升序排序。  Sample Input 55 61 410 106 98 10 Sample Output 1 45 10 Problem Source SDOI  #include <stdio.h>#include <malloc.h> typedef struct Node{ int i;  int j;  struct Node *next;}QNODE;QNODE *head = NULL,*temp = NULL,*ahead = NULL; int enter(){ int n,m,max;  QNODE *qtemp;   head = temp = (QNODE*)malloc(sizeof(QNODE));  head -> next = NULL;  scanf("%d",&m);  for(max = 0,n = 0; n < m; n ++) { scanf("%d %d",&temp -> i,&temp -> j);   if( temp -> j > max )  max = temp -> j;   qtemp = (QNODE*)malloc(sizeof(QNODE));   qtemp -> next = NULL;   temp -> next = qtemp;   temp = qtemp; }  return max;} void select_part(int *i,int *j){ QNODE *qtemp;  int s;     qtemp = temp = head;  if( !head -> next )   { *i = temp -> i ;   *j = temp -> j;   free( head );   head = NULL;   return ; }    s = temp -> i;  while( temp -> next ) { if( temp -> i  < s )  { s = temp -> i;    qtemp = temp;  }   temp = temp -> next; }  if( qtemp != head ) { *i = qtemp -> i;   *j = qtemp -> j;   temp = head;   while( temp -> next != qtemp )    temp = temp -> next;   temp -> next = qtemp -> next;   free( qtemp ); }  else  { *i = qtemp -> i;   *j = qtemp -> j;   head = qtemp -> next;   free( qtemp ); }}   void compulate(int max){ int i,j,x,y;  QNODE *atemp;   select_part(&i,&j);  ahead = atemp = (QNODE*)malloc(sizeof(QNODE));  ahead -> next = NULL;  while( j < max ) { select_part(&x,&y);   if( x >= i && y <= j )  continue;   else if( x <= j && y > j )   j = y;   else if( x > j  )   { atemp -> i = i;     atemp -> j = j;     i = x;     j = y;     atemp -> next = (QNODE*)malloc(sizeof(QNODE));     atemp = atemp -> next;   } }  atemp -> i = i;  atemp -> j = j;  atemp -> next = NULL;} void out(){ temp = ahead;   while( temp ) { printf("%d %d\n",temp -> i,temp -> j);   temp = temp -> next; }} void free_mem(){ while( ahead ) { temp = ahead;   ahead = ahead -> next;   free(temp); }} int main(){ int max;    max = enter();   compulate( max );   out();   free_mem();   return 0;}

评论