概述
算法导论16.1---3
原题如下：用很多个教室对一组活动进行调度，希望用最少的教室来调度所有的活动
算法导论上面的提示是区间图着色。大家不要错误的认为是图着色。图着色最多可以用四个颜色解决 (参考四色定理) 。
现假如我有五个活动8:00到11:00,8.30到11.30,9.00到10.30,9.00到11.00,10.00到12.00，现在这五个活动明显要五个教室，这五个活动全部重叠在一起。
算法一：用贪心，假设m个教室，初始化m=0，用两个链表，一个表示的是在时刻t空闲的教室，一个表示在时刻t busy的教室，当活动ai开始时从空闲链表摘下放到busy中，结束时还回去，当空闲链表没有教室时，m++教室多一个，最后m就是最少需要的教室数目。对n个活动的2n个端点排序，一遍扫描过去，遇到start[i],从空闲链表取教室，没有空闲链表时，m++，遇到end[i],放回空闲链表。
算法二：这个题目可以取巧，最少的教室数目是由重叠度最大的时间点决定的。
如果时间是整数更好求了，用一个时间数组time[]记录，在每一个活动ai中时间区间的，time[]++,最后统计最大的就ok了。
For(int i=ai的start，i<=ai的end，i++）
Time[i]++;
一遍扫描过去就好了。
Author：zzy
参考：算法导论
可能会有错误，请大家指正。
最后
以上就是优秀钢铁侠为你收集整理的贪心算法之活动选择问题的全部内容，希望文章能够帮你解决贪心算法之活动选择问题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复