区间 
 
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
5
5 6
1 4
10 10
6 9
8 10
 
Sample Output
1 4
5 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;
}

评论