會場安排問題貪心演算法

① 下題貪心演算法一種形式望解得合理安排會議最多編寫程序，輸入10個會議開始和結束時間，輸出選中的會議。。

王才」使用甄後與曹植的愛情故事。見《文選·洛神賦》李善注說：魏東阿王曹植曾求娶甄氏為妃，曹操卻將她許給曹丕。甄後被讒死後，曹丕將她的遺物玉帶金鏤枕送給曹植。曹植離京歸國途經洛水，夢見甄後對他說：「我本托心君王，其心不遂。此枕是我在家時從嫁，前與五官中郎將（曹丕），今與君王。」曹植感其事作《感甄賦》，

② C語言程序問題——活動安排問題

題目出得不嚴密，題目要求是「計算安排的活動最多時會場使用時間」，但當「安排的活動最多」有多種安排方式，題目中卻沒說輸出這多種方式中的哪一種的會場使用時間。例如 ：當有3項活動要安排，開始時間和結束時間分別是1 2、3 5、4 5，這時可以安排第一項和第二項活動，也可以安排第一項和第三項活動，前者的會場使用時間是5，後者是4，這時是輸出4還是5，題目中沒用指出。先假設測試數據不會出現上述情況，則利用貪心演算法求解活動安排問題是一種最常用的方法：#include<stdio.h>
#include<stdlib.h>
struct activity
{
int start;
int end;
}act[8501];
int comp(const void *p, const void *q)
{
struct activity *a=(struct activity *)p;
struct activity *b=(struct activity *)q;
return a->end-b->end;
}
int main()
{
int i,k,res,e;
while(scanf("%d",&k)!=EOF)
{
for(i=0;i<k;i++) scanf("%d%d",&act[i].start,&act[i].end);
qsort(act,k,sizeof(act[0]),comp);
res=act[0].end-act[0].start+1;
e=act[0].end;
for(i=1;i<k;i++)
{
if(act[i].start>e)
{
res+=act[i].end-act[i].start+1;
e=act[i].end;
}
}
printf("%d\n",res);
}
return 0;
}

③ 會場安排問題

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

解活動安排問題的貪心演算法greedySelector :
public static int greedySelector(int [] s, int [] f, boolean a[])
{
int n=s.length-1;
a[1]=true;
int j=1;
int count=1;
for (int i=2;i<=n;i++) {
if (s[i]>=f[j]) {
a[i]=true;
j=i;
count++;
}
else a[i]=false;
}
return count;
}
由於輸入的活動以其完成時間的非減序排列，所以演算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該演算法的貪心選擇的意義是使剩餘的可安排時間段極大化，以便安排盡可能多的相容活動。
演算法greedySelector的效率極高。當輸入的活動已按結束時間的非減序排列，演算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。

活動安排問題源代碼：
#include <iostream>

#include <vector>
#include <algorithm>

using namespace std;

struct point
{
int t;
bool f;
};

bool cmp(point x,point y)
{
return x.t<y.t;
}

int greedy(vector<point> x)
{
int max=0,cur=0,n=x.size();
sort(x.begin(),x.end(),cmp);
for(int i=0;i<n;i++)
{
if(x[i].f)
cur++;
else
cur--;
if(cur>max)
max=cur;
}
return max;
}

int main()
{
vector<point> x;
int n,i;
point temp;
while(cin>>n,n)
{
for(i=0;i<n;i++)
{
temp.f=true;
cin>>temp.t;
x.push_back(temp);
temp.f=false;
cin>>temp.t;
x.push_back(temp);
}
cout<<greedy(x)<<endl;
x.clear();
}
return 0;
}

④ 貪心演算法的會場安排問題

查找有沖突的活動，將有沖突的放到第二個會場。
繼續查找有沖突的活動，放到第三個會場。
就是貪心么。先按第一會場排，然後排第二會場、……
不知道是不是最優解。暫時還想不到反例。

⑤ 貪心演算法 活動安排問題

這道題的貪心演算法比較容易理解，我就不多說明了，只是提到一下演算法思路1、建立數學模型描述問題。我在這里將時間理解成一條直線，上面有若干個點，可能是某些活動的起始時間點，或終止時間點。在具體一下，如果編程來實現的話，將時間抽象成鏈表數組，數組下標代表其實時間，該下標對應的鏈表代表在這個時間起始的活動都有哪些，具體參照程序注釋。2、問題分解。為了安排更多的活動，那麼每次選取佔用時間最少的活動就好。那麼從一開始就選取結束時間最早的，然後尋找在這個時間點上起始的活動，以此類推就可以找出貪心解。程序代碼：#include<stdio.h>
struct inode //自定義的結構體
{
int end; //表示結束時間
inode *next; //指向下一個節點的指針
};int main()
{
inode start[10001],*pt;
int a,b,i,num=0; //num負責計數，i控制循環，a，b輸入時候使用
for(i=0;i<10001;i++) //初始化
{
start[i].next=NULL;
}
while(scanf("%d %d",&a,&b)) //輸入並建立數據結構
{
if(a==0&&b==0) break;
pt=new inode; //創建新的節點，然後將該節點插入相應的位置
pt->end=b;
pt->next=start[a].next;
start[a].next=pt;
}
i=0;
while(i<10001) //進行貪心演算法，i表示當前時間
{
if(start[i].next==NULL)
{
i++; //該時間無活動開始
}
else
{
int temp=10001; //臨時變數，存儲該鏈表中最早的終止時間
for(pt=start[i].next;pt!=NULL;pt=pt->next)
{
if(pt->end<temp)
{
temp=pt->end;
}
}
i=temp; //將當前時間設置成前一子問題的終止時間
num++;
}
}
printf("%d\n",num); //列印結果
return 0;
}代碼並不一定是最快速的，但是可以求出貪心解，如果你做的是ACM編程題目，不保證能AC注釋我盡力寫了，希望對你有幫助。

⑥ OJ貪心演算法，活動安排，求大神解答

按結束時間從小到大排序，之後從開始貪心即可

⑦ 貪心演算法之會場安排問題

三星演算法之間最好還是不要安排互相的問題，這樣不利於你們倆的關系的便有好。

⑧ 請高手進來解答一下這道演算法設計與分析的題目，謝謝了！！

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

在下面所給出的解活動安排問題的貪心演算法greedySelector:

publicstaticintgreedySelector(int[]s,int[]f,booleana[])

{

intn=s.length-1;

a[1]=true;

intj=1;

intcount=1;

for(inti=2;i<=n;i++){

if(s[i]>=f[j]){

a[i]=true;

j=i;

count++;

}

elsea[i]=false;

}

returncount;

}

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

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

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

i 1 2 3 4 5 6 7 8 9 10 11

S[i] 1 3 0 5 3 5 6 8 8 2 12

f[i] 4 5 6 7 8 9 10 11 12 13 14

⑨ 會場安排問題，java的實現

您好，提問者：
會議數組那麼肯定存放一個對象，我舉個簡單的Person例子：

importjava.util.Comparator;
importjava.util.Iterator;
importjava.util.TreeSet;


publicclassTest{
	publicstaticvoidmain(String[]args){
		//使用匿名內部類進行排序
		TreeSet<Person>set=newTreeSet<Person>(newComparator<Person>(){
			publicintcompare(Persono1,Persono2){
				intnum=newInteger(o2.end).compareTo(o1.end);
				returnnum;
			}
		});
		set.add(newPerson(1,3));
		set.add(newPerson(2,5));
		System.out.println("開始時間	結束時間");
		for(Iterator<Person>it=set.iterator();it.hasNext();){
			Personp=it.next();
			System.out.println(p.start+"	"+p.end);
		}
	}
}
classPerson{
	intstart;
	intend;
	publicPerson(intstart,intend){
		this.start=start;
		this.end=end;
	}
}

//輸出結果：

開始時間 結束時間

2 5

1 3

⑩ 採用貪心演算法進行安排。對演算法的時間和空間復雜度進行分析

時間主要是 排序用時了，快速排序 一般是 o(n*logn)
空間 復雜度基本上是 0(1)