編程之美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 閱讀(185) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

編程之美1.9(三) 最大效率安排會議

另一種方法解決高效率安排會議問題