greedyselect.c

本代码用贪心算法实现会议安排的最佳顺序

Qsort(int f[],int c[],int low,int high)
{ int i,j,lab;
  i=low,j=high;
  lab=c[low];
  while(i<j)
  { while(i<j&&f[c[j]]>f[lab])
      j--;
     if(i<j)
     { c[i]=c[j];  i++; }
    while(i<j&&f[c[i]]<f[lab])
     i++;
     if(i<j)   { c[j]=c[i]; j--;}
  }
  c[i]=lab;
  if(low<i)
   Qsort(f,c,low,i-1);
  if(high>j)
   Qsort(f,c,j+1,high);
}/*Qsort*/
int greedyselet(int s[],int f[],int n)
{ int i,j,count;
  int *a,*c;
  a=(int *)malloc((n+1)*sizeof(int));
  c=(int *)malloc((n+1)*sizeof(int));
  for(i=1;i<=n;i++)
     c[i]=i;
  Qsort(f,c,1,n);
  a[1]=1; j=1;count=1;
  for(i=2;i<=n;i++)
   { if(s[c[i]]>=f[c[j]])
       { a[i]=1;
          j=i;
           count++;
        }
     else  a[i]=0;
   }
  for(i=1;i<=n;i++)
    if(a[i]==1)
     printf("%d ",c[i]);
  free(a);  free(c);
  return(count);
}/*greedyselect*/
main()
{ int n,i,*s=0,*f=0;
  char ch;
  printf("Please input the number of job:\n");
  scanf("%d",&n);
  s=(int *)malloc((n+1)*sizeof(int));
  f=(int *)malloc((n+1)*sizeof(int));
  printf("\nPlease input the starting time:\n");
  for(i=1;i<=n;i++)
   scanf("%d%c",&s[i],&ch);
  printf("Please input the endint time:\n");
  for(i=1;i<=n;i++)
   scanf("%d%c",&f[i],&ch);
  i=greedyselet(s,f,n);
  printf("\nThere are %d acts avaelable",i);
  getch();
}/*main greedyselect*/