會場安排問題

時間限制：3000?ms ?|? 內存限制：65535?KB 難度：4 描述

學校的小禮堂每天都會有許多活動，有時間這些活動的計劃時間會發生沖突，需要選擇出一些活動進行舉辦。小劉的工作就是安排學校小禮堂的活動，每個時間最多安排一個活動。現在小劉有一些活動計劃的時間表，他想盡可能的安排更多的活動，請問他該如何安排。
輸入

第一行是一個整型數m(m<100)表示共有m組測試數據。
每組測試數據的第一行是一個整數n(1<n<10000)表示該測試數據共有n個活動。
隨后的n行，每行有兩個正整數Bi,Ei(0<=Bi,Ei<10000),分別表示第i個活動的起始與結束時間（Bi<=Ei)

輸出

對于每一組輸入，輸出最多能夠安排的活動數量。
每組的輸出占一行

樣例輸入

2 2 1 10 10 11 3 1 10 10 11 11 20

樣例輸出

1 2

提示注意：如果上一個活動在T時間結束，下一個活動最早應該在T+1時間開始。

解題思路：這是一個貪心法中選擇不相交區間的問題。先對活動結束時間從小到大排序，排序的同時活動的起始時間也要跟著變化。而且，結束時間最小的活動一定會安排，不然這段時間就白白浪費了。后一個活動的起始時間如果比前一個活動的結束時間大，即兩個活動沒有相交時間，就把這個活動也安排上。就這樣一直找到結束時間最大的，輸出時間數目即可。排序時可用下面的方法，排序的同時起始時間也跟著變了。

int cmp(struct nn a1,struct nn a2)
{
if(a1.c!=a2.c)
return a1.c<a2.c;
? ? if(a1.b!=a2.b)
return a1.b<a2.b;
}

如果輸入

0 6

3 4

1 9

2 8

則排序后的結果就是

3 4

0 6

2 8

1 9

AC代碼：

#include<stdio.h> #include<algorithm> using namespace std; struct nn {int b,c; }a[10005]; /*定義結構體數組*/ int cmp(struct nn a1,struct nn a2) { if(a1.c!=a2.c) return a1.c<a2.c;if(a1.b!=a2.b) return a1.b<a2.b; } /*排序*/ int main() { int n,i,p,m; scanf("%d",&m); while(m--) {scanf("%d",&n);for(i=0;i<n;i++) scanf("%d %d",&a[i].b,&a[i].c);sort(a,a+n,cmp); /*調用排序函數*/p=a[0].c;int count=1;for(i=1;i<n;i++)if(a[i].b>p){count++;p=a[i].c;} /*后一個活動起始時間比前一個結束時間大，不相交，count加1*/printf("%d\n",count); } return 0; }

?

?

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的NYOJ 14 会场安排问题 贪心算法 之 选择不相交区间的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。