算法设计与分析课件 13 会议安排_第1页
算法设计与分析课件 13 会议安排_第2页
算法设计与分析课件 13 会议安排_第3页
算法设计与分析课件 13 会议安排_第4页
算法设计与分析课件 13 会议安排_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析本节要点CONTENTS会议安排会议安排会议安排问题要求在有限的时间内召开更多的会议（任何两个会议不能同时进行）。在会议安排中，每个会议i都有起始时间bi和结束时间ei，且bi<ei，即一个会议进行的时间为半开区间[bi，ei）。如果[bi，ei）与[bj，ej）均在“有限的时间内”，且不相交，则称会议i与会议j相容的。会议安排问题要求在所给的会议集合中选出最大的相容活动子集，即尽可能在有限的时间内召开更多的会议。会议安排会议安排{1，4，6，8，9}，{2，4，7，8，9}都是能安排最多的会议集合。会议数最多，需要选择最多的不相交时间段。可以尝试以下贪心策略：（1）最早开始时间且与已安排的会议相容的会议。（2）持续时间最短且与已安排的会议相容的会议。（3）最早结束时间且与已安排的会议相容的会议。算法设计会议安排最好选择那些开始时间要早，而且持续时间短的会议，即最早开始时间+持续时间最短，就是最早结束时间。贪心策略：每次从剩下的会议中选择具有最早结束时间且与已安排的会议相容的会议。会议安排（1）初始化。将n个会议的开始时间、结束时间存放在结构体数组中然后按结束时间非递减排序，结束时间相等时，按开始时间非递增；（2）根据贪心策略选择第一个具有最早结束时间的会议，用last记录刚选中会议的结束时间；（3）依次从剩下未安排的会议中选择，如果会议i开始时间大于等于last，那么会议i可以安排，更新last为刚选中会议的结束时间；否则，舍弃会议i，检查下一个会议是否可以安排。会议安排会议安排会议安排贪心选择过程：算法实现会议安排算法分析时间复杂度：排序函数sort的平均时间复杂度为O(nlogn)。选择会议，需要遍历整个会议列表，时间复杂度为O(n)，总时间复杂度为O(n+nlogn)=O

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论