贪心算法-会场安排问题
更新时间:2023-05-01 12:35:01 阅读量: 实用文档 文档下载
。
计算机算法设计与分析(第3版)
128页
算法实现题4-1 会场安排问题
问题描述:假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务:对于给定的k 个待安排的活动,编程计算使用最少会场的时间表。Input 输入数据是由多组测试数据组成。每组测试数据输入的第一行有1 个正整数k,表示有k 个待安排的活动。接下来的k 行中,每行有2 个正整数,分别表示k 个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。Output 对应每组输入,输出的每行是计算出的最少会场数。
源代码:
#include
int fnPartition(int a[], int low, int high)
{
int i,j;
int x = a[low];
i = low;
j = high;
while(i
{
-可编辑修改-
。
while(i
if(i
while(i
if(i
}
a[i] = x;
return i;
}
void fnQuickSort(int a[],int low, int high) {
int pos;
if(low < high)
{
pos = fnPartition(a,low,high);
fnQuickSort(a,low,pos-1);
fnQuickSort(a,pos+1,high);
}
}
int fnSchedule(int a[],int b[],int s,int e) {
int n=0; int i=s+1; if (a[s]>-1)
-可编辑修改-
。
{
n = 1;
for(; i <=e; i++) if(a[i]>=b[s]) s++; else n++;
}
return n;
}
int main(void)
{
int n,i;
while(1 == scanf("%d",&n))
{
int *st = new int [n];
int *et = new int [n];
for (i = 0; i
fnQuickSort(et,0,n-1);
printf("%d\n",fnSchedule(st,et,0,n-1));
delete []st; delete []et;
} return 0;
}
输入文件示例:输出文件示例:
-可编辑修改-
。
5 3 1 23
12 28
25 35
27 80
36 50
-可编辑修改-
正在阅读:
贪心算法-会场安排问题05-01
3.1社会主义建设在探索中曲折发展05-31
实习班主任工作日记02-12
财务基础知识及借贷关系06-27
北师大版四年级下册方程专项练习题01-29
山东电力集团公司110kV-500kV变电站智能化典型配置方案06-04
我们班的“倒霉大王”作文600字06-29
2008-2009第二学期《外贸单证实务》A(陈广)03-02
陈小丽《哲学与人生》教案(精品)10-12
恋爱中的经济学分析(四)08-14
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 贪心
- 会场
- 算法
- 安排
- 问题
- 12注会会计·张筱冰强化班·【016】第十六讲
- 绿色食品大蒜生产技术操作规程
- 小心理财中的“财富黑洞”
- 小学未成年人思想道德建设工作总结汇报
- 八年级初二地理会考试卷及答案
- 初中必备英语单词大全汇总
- 国际经济与贸易毕业论文题目精选
- 傲慢与偏见简·奥斯汀读后感600字左右范文
- 成人教育JSP应用程序设计期末考试试卷及复习题参考答案
- 20172018学年高二政治教师下册工作计划
- 2017年春华师大版九年级数学下期中检测题含答案
- 【教育学习文章】二年级语文上3美丽的呼伦湖教案作业题(冀教版)
- 区委书记在区人民检察院领导班子见面会上的讲话
- 2014年国际贸易实务考试试题
- 2021年高考数学复习 第84课时 第十章 排列、组合和概率二项式定理(1)名师精品教案
- 医院工作人员的承诺书
- 输变电工程安全文明施工设施配置标准
- 森林抚育作业任务设计
- 最新初中描写秋天的作文20篇
- 最新部编人教版二年级语文上册四单元试卷及答案推荐(三套)