• 注册
当前位置:1313e > 默认分类 >正文

活动安排(选择)问题拓展

1.区间图着色 Interval-graph Coloring Problem
假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有的活动。请给出一个有效的贪心算法,来确定最少教室数。(这个问题也被称为区间图着色(interval-graph coloring)问题。我们可作出一个区间图,其顶点为已知的活动,其边连接着不兼容的活动。为使任两个相邻结点的颜色均不相同,所需的最少颜色数对应于找出调度给定的所有活动所需的最少教室数。)
模拟思路:
对于活动的开始时间和结束时间点进行排序。维护两个盒子,busy_classroom_num、free_classroom_num。扫描排序的时间t,若t为一个活动的开始时间,我们从free_classroom_num–,busy_classroom_num++。如果,在free_classroom_num–之前,free_classroom_num已经为0,则新生成一个教室,直接busy_classroom_num++。若t为一个活动的结束时间,我们从busy_classroom_num–,free_classroom_num++。时间扫描完毕,free_classroom_num为最少的教室数。
2.值之和最大的兼容活动子集
待学习:http://m.blog.csdn.net/blog/shakingWaves/23026571#

本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 162202241@qq.com 举报,一经查实,本站将立刻删除。

最新评论

欢迎您发表评论:

请登录之后再进行评论

登录
相关推荐