首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

会场安排有关问题急求解答

2013-08-01 
会场安排问题急求解答先说一下,算法新手想问题可能比较怪,为了说清楚我的想法,可能会讲得比较多,希望能有

会场安排问题急求解答
先说一下,算法新手想问题可能比较怪,为了说清楚我的想法,可能会讲得比较多,希望能有大神解答疑问。知道怎么做的直接从“3.我的思路”开始看。

1.问题描述:

假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 (这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 对于给定的k个待安排的活动,计算使用最少会场的时间表

Input 第一行有1 个正整数k,表示有 k个待安排的活动。接下来的k行中,每行有 2个正整数,分别表示 k个待安排的活动开始时间和结束时间。时间以0点开始的分钟计。
Output  输出最少会场数
Sample Input

1 23 
12 28 
25 35 
27 80 
36 50
Sample Output
3

2. 解答  http://www.cppblog.com/zhangwangcz/archive/2012/10/19/193502.html

3.我的思路:
 我的想法是这样的,把每个活动看成一个整体,然后①按结束时间排序。②取出一个未被安排的活动,然后取出下一个未被安排且与上一个取出活动相容的活动。如果所有活动都安排完,则结束。如果仍有活动未安排,继续执行②。
  这样结束的话,有多少组相容活动就用多少会场。
  当然这个解法是错的,谁能告诉我错在哪里?
   算法 贪心算法 会场安排问题 新手求解
[解决办法]
算法导论中的问题,设start[i]是第i的活动的开始时间,end[i]是结束时间,贪心原则为对于一个待安排的会场,当前结束时间最早的一个活动一定应该是第一个被安排的
[解决办法]
楼主,你说你的算法不对,请把你的输入和输出贴出来,让我们看看

热点排行