/*日期:2011-10-17
作者:xiaosi
题目:会场安排问题(贪心)
题目链接:
http://acm.nyist.net/JudgeOnline/problem.php?pid=14
*/
#include<iostream>
#include<cstdio>
#include<stdlib.h>
using namespace std;
struct Activity
{
int begin;
int end;
}A[10000];
int cmp(const void *a,const void *b)
{
struct Activity *c = (Activity *)a;
struct Activity *d = (Activity *)b;
return c->end - d->end;
}
int Selector(Activity A[],int n)
{
int i,j=0,count=1;
for(i=1;i<n;i++)
{
if(A[i].begin > A[j].end)
{
count++;
j=i;
}
}
return count;
}
int main()
{
int N;
while(scanf("%d",&N)!=EOF)
{
while(N--)
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d %d",&A[i].begin,&A[i].end);
}
qsort(A,n,sizeof(A[0]),cmp);
printf("%d\n",Selector(A,n));
}
}
}
分享到:
相关推荐
用贪心算法解决会场按排问题,用netbeans6.8做的。已经编译通过没任何错误,JAVA 源文件。
贪心算法之会场安排问题,直接可运行,python文件
会场安排,用贪心解,里面的排序用的是快排,如果感觉效率不高可以换。
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于...
会议安排问题(贪心算法) VC下调试OK
设有n个会议的集合C={1,2,…,n},其中每个会议都要求使用同一个资源(如会议室),而在同一时间内只能有一个...会场安排问题要求在所给的会议集合中选出最大的相容活动子集,也即尽可能地选择更多的会议来使用资源。
假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同...
在会场资源足够多的条件下,对n个活动进行安排,以达到最少会场使用量。文中对这个问题进行了算法分析,并给出了C语言实现。
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于...
贪心算法 会场安排问题.doc
会场安排问题 超实用简洁 算法设计与分析 贪心法解决
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于...
假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 用C++语言实现
假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。
贪心算法 会场安排问题 算法设计分析.doc
贪心算法会场安排问题算法设计分析
贪心算法(会场安排)源代码.txt
热心学姐来送福利啦哈哈哈哈哈哈哈哈哈哈哈哈哈,西北农林科技大学的算法分析实验报告,
贪心算法,会场安排,可直接运行,本人已调试成功