jake1036

My Links

Blog Stats

Posts - 101
Stories - 0
Comments - 23
Trackbacks - 0

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

閱讀排行榜

評論排行榜

編程之美1.9(二) 高效率地安排會面

高效率地安排會面

一問題分析：
     問題描述：
(1) 面試的時候，每次會面都有一個開始時間b[i] 和結束時間e[i] 。
(2) 現在有一組面試時間數據，現在要求每一個有沖突的時間，都不允許安排在
      同一個地點，求出最小需要安排的地點數目。

問題分析：
(1) 首先按照開始時間，將面試時間遞增排列。
(2) 依次從第一個約會開始時間開始。

const int N = 4 ;

struct Time

{

int begin ; //開始時間

int end ; //結束時間

} ;

bool forbit[N] ; //禁止數組，為false的時候，表示當前該顏色可以使用

int maxcolors ; //當前最大的顏色數目

Time times[N] ;

int color[N] = {0} ;

int cmp(const void * a , const void * b)

{

return ((Time*)a)->begin - ((Time*)b)->begin ;

}

void init()

{

for(int i = 0 ; i < N ; i++)

{

cin>>times[i].begin>>times[i].end ; //輸入開始時間和結束時間

}

qsort(times ,N , sizeof(Time) ,cmp) ;

//for(i = 0 ; i < N ;i++)

// forbit[i] = false ;

}

bool overlap(const Time & a, const Time & b)

{

if(b.begin >= a.begin && b.begin < a.end )

return true ;

return false ;

}

int arrange()

{

maxcolors = 0 ;

int i , j , k ;

for(i = 0 ; i < N ;i++) //循環每一個約會安排

{

for(k = 0 ; k < maxcolors ;k++)

{

forbit[k] = false ;

}

//判斷在i之前的節點是否是與i節點有重合的部分

for(j = 0 ; j < i ;j++)

{

if(overlap(times[j] , times[i])) //判斷兩者是否相交

{

forbit[color[j]] = true ;

}

for(k = 0 ; k < maxcolors ;k++)

{

if(!forbit[k])

break ;

}

if(k < maxcolors)

color[i] = k ;

else

color[i] = maxcolors++ ;

}

return maxcolors ;

}

int main()

{

init() ;

int max = arrange() ;

cout<<max<<endl ;

system("pause") ;

return 0 ;

}

posted on 2011-06-30 14:37 kahn 閱讀(387) 評論(0) 編輯收藏引用所屬分類: 算法相關

只有注冊用戶登錄后才能發表評論。


相關文章: 9-24MTK一面二面微軟筆試總結 2011-09-07xx移動創業公司筆試題編程之美2.7 最大公約數 O(n)實現刪除兩個數組中的共同元素編程之美1.9(二) 高效率地安排會面分組背包問題（六）二維背包問題（五）多重背包（三）完全背包問題 <二>

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品