会场安排问题急求解答
先说一下,算法新手想问题可能比较怪,为了说清楚我的想法,可能会讲得比较多,希望能有大神解答疑问。知道怎么做的直接从“3.我的思路”开始看。
1.问题描述:
假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 (这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 对于给定的k个待安排的活动,计算使用最少会场的时间表
Input 第一行有1 个正整数k,表示有 k个待安排的活动。接下来的k行中,每行有 2个正整数,分别表示 k个待安排的活动开始时间和结束时间。时间以0点开始的分钟计。
Output 输出最少会场数
Sample Input
5
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]是结束时间,贪心原则为对于一个待安排的会场,当前结束时间最早的一个活动一定应该是第一个被安排的
[解决办法]
楼主,你说你的算法不对,请把你的输入和输出贴出来,让我们看看