當前位置:首頁 > 芯聞號 > 充電吧
[導讀]活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合,是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動

活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合,是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。

??? 設有n個活動的集合E={1,2,…,n},其中每個活動都要求使用同一資源,如演講會場等,而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si<fi 。如果選擇了活動i,則它在半開時間區(qū)間[si, fi]內(nèi)占用資源。若區(qū)間[si, fi]與區(qū)間[sj, fj]不相交,則稱活動i與活動j是相容的。也就是說,當si≥fj或sj≥fi時,活動i與活動j相容。

????由于輸入的活動以其完成時間的非減序排列,所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上,按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說,該算法的貪心選擇的意義是使剩余的可安排時間段極大化,以便安排盡可能多的相容活動。

????此算法的效率極高。當輸入的活動已按結束時間的非減序排列,算法只需O(n)的時間安排n個活動,使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列,可以用O(nlogn)的時間重排。

例:設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下:

?

算法的計算過程如圖所示。圖中每行相應于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動,而空白長條表示的活動是當前正在檢查相容性的活動。

?

若被檢查的活動i的開始時間Si小于最近選擇的活動j的結束時間fi,則不選擇活動i,否則選擇活動i加入集合A中。

?????貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題,貪心算法卻總能求得的整體最優(yōu)解,即它最終所確定的相容活動集合A的規(guī)模最大。這個結論可以用數(shù)學歸納法證明。

?

#include#include#includeusing?namespace?std;

typedef?struct{
	int?s;//開始時間
	int?f;//結束時間
}node;

int?cmp(const?void?*a,?const?void?*b)
{
	return?((node?*)a)->f-((node?*)b)->f;//按結束時間升序排列
}

void?main()
{
	int?i,?j=0,?n;
	int?count=1;
	node?a[100];	
	cin>>n;
	for(i=0;?i>a[i].s>>a[i].f;

	qsort(a,?n,?sizeof(a[0]),?cmp);

	for(i=1;?ia[j].f)
		{
			j=i;
			count++;
		}
	}

	cout<<count<<endl;
}


本站聲明: 本文章由作者或相關機構授權發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或將催生出更大的獨角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉型技術解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關鍵字: 汽車 人工智能 智能驅動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務中斷的風險,如企業(yè)系統(tǒng)復雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務連續(xù)性,提升韌性,成...

關鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關鍵字: 華為 12nm EDA 半導體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權最終是由生態(tài)的繁榮決定的。

關鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務引領增長 以科技創(chuàng)新為引領,提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強核心競爭優(yōu)勢...

關鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術學會聯(lián)合牽頭組建的NVI技術創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術創(chuàng)新聯(lián)...

關鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(集團)股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關鍵字: BSP 信息技術
關閉
關閉