jake1036

编程之美1.9(三) 最大效率安排会议

 另一种方法解决高效率安排会议问题

  一 方法分析：
      考虑一种优化算法，将所有的begin 和 end 共同参与排序。
      然后依次遍历整个的2*N个数组元素，若是遇到begin则将使用的颜色数目加一。
      若是遇到的是end类型，则将使用的颜色数目减一。
      在内存中，保留最大使用的颜色数目。
      整个的时间的复杂度是o(n * logn)
 二 代码如下：
 

#include <iostream>
 using namespace std ; 
 
 const int BEGIN = 1 ;
 const int END = 2 ;
 const int N = 4 ;
 struct Time
 {
    int type ;
    int time ;    
 } ;
 
 Time times[N + N] ;
 
 int cmp(const void * a , const void * b)
 {
     return ((Time*)a)->time - ((Time*)b)->time ;
     
 }
 void init()
 {
    for(int i = 0 ; i < N + N;i++)  
     {       
       cin>>times[i].time  ;  
       if(i%2 == 0)          
        times[i].type = BEGIN ;     
       else     
        times[i].type = END ;
            
     } 
     
     qsort(times  , N +N, sizeof(Time) , cmp) ;
     
     for(int i = 0 ; i < N + N;i++)  
     {       
       cout<<times[i].time<<"type: "<<times[i].type<<"  "  ;           
     } 
 }
 
 int arrange()
 {
   init() ;
   int usingcolor = 0 ;
   int max = 0 ;
   for(int i = 0 ; i < N + N ;i++)
   {
      if(times[i].type == BEGIN)
       {
         usingcolor++ ; 
         if(max < usingcolor)
           max = usingcolor ;   
       }     
       else
         usingcolor-- ;     
   }      
   
   return max ;
 }
 
 int main()
 {
   int color = arrange() ;
   cout<<color<<endl ;
   system("pause") ;
   return 0 ;    
 }


  

posted on 2011-06-30 15:31 kahn 阅读(180) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理