跳转到内容
主菜单
主菜单
移至侧栏
隐藏
导航
首页
最近更改
随机页面
MediaWiki帮助
代码酷
搜索
搜索
中文(中国大陆)
外观
创建账号
登录
个人工具
创建账号
登录
未登录编辑者的页面
了解详情
贡献
讨论
编辑“︁
区间调度问题
”︁
页面
讨论
大陆简体
阅读
编辑
编辑源代码
查看历史
工具
工具
移至侧栏
隐藏
操作
阅读
编辑
编辑源代码
查看历史
常规
链入页面
相关更改
特殊页面
页面信息
外观
移至侧栏
隐藏
您的更改会在有权核准的用户核准后向读者展示。
警告:
您没有登录。如果您进行任何编辑,您的IP地址会公开展示。如果您
登录
或
创建账号
,您的编辑会以您的用户名署名,此外还有其他益处。
反垃圾检查。
不要
加入这个!
= 区间调度问题 = 区间调度问题(Interval Scheduling Problem)是'''贪心算法'''(Greedy Algorithm)中的经典问题之一,广泛应用于任务调度、资源分配等场景。该问题的目标是:在给定的若干区间(如时间区间)中,选择尽可能多的互不重叠的区间。 == 问题定义 == 给定一组区间 <math>S = \{ [s_1, f_1), [s_2, f_2), \dots, [s_n, f_n) \}</math>,其中 <math>s_i</math> 表示区间的起始点,<math>f_i</math> 表示区间的结束点。目标是选择一个子集 <math>S' \subseteq S</math>,使得 <math>S'</math> 中的区间互不重叠,且 <math>|S'|</math>(即子集的大小)最大化。 === 示例 === 假设有以下区间: * <math>[1, 3)</math> * <math>[2, 4)</math> * <math>[3, 5)</math> * <math>[4, 6)</math> 最优解是选择 <math>[1, 3)</math> 和 <math>[3, 5)</math> 或 <math>[2, 4)</math> 和 <math>[4, 6)</math>,因为这两组区间互不重叠且数量最多。 == 贪心算法解法 == 贪心算法通过局部最优选择逐步构造全局最优解。对于区间调度问题,通常有以下几种贪心策略: 1. '''最早开始时间优先'''(Earliest Start Time First) 2. '''最短区间优先'''(Shortest Interval First) 3. '''最少冲突优先'''(Fewest Conflicts First) 4. '''最早结束时间优先'''(Earliest Finish Time First) 其中,'''最早结束时间优先'''策略被证明能获得最优解。 === 算法步骤 === 1. 将所有区间按结束时间 <math>f_i</math> 升序排序。 2. 初始化一个空集合 <math>S'</math>,并选择第一个区间加入 <math>S'</math>。 3. 遍历剩余的区间,每次选择一个与 <math>S'</math> 中最后一个区间不重叠的区间(即其开始时间 <math>s_i \geq f_{\text{last}}</math>),并将其加入 <math>S'</math>。 4. 返回 <math>S'</math>。 === 代码实现 === 以下是使用 Python 实现的贪心算法: <syntaxhighlight lang="python"> def interval_scheduling(intervals): # 按结束时间升序排序 intervals.sort(key=lambda x: x[1]) selected = [] last_finish = -float('inf') for start, finish in intervals: if start >= last_finish: selected.append((start, finish)) last_finish = finish return selected # 示例输入 intervals = [(1, 3), (2, 4), (3, 5), (4, 6)] result = interval_scheduling(intervals) print("选中的区间:", result) </syntaxhighlight> '''输出:''' <pre> 选中的区间: [(1, 3), (3, 5)] </pre> === 算法分析 === * '''时间复杂度''':排序步骤为 <math>O(n \log n)</math>,遍历区间为 <math>O(n)</math>,因此总时间复杂度为 <math>O(n \log n)</math>。 * '''空间复杂度''':<math>O(1)</math>(如果不考虑存储结果的空间)。 == 实际应用案例 == 区间调度问题的应用场景广泛,例如: 1. '''会议室预订''':选择最多不冲突的会议安排。 2. '''课程表安排''':避免课程时间冲突。 3. '''任务调度''':在有限资源下执行最多的任务。 === 示例:会议室预订 === 假设某公司有多个会议请求,每个会议有开始和结束时间。目标是安排最多的会议,且会议室同一时间只能用于一个会议。 给定会议时间: * 会议 A: [9:00, 10:00) * 会议 B: [9:30, 10:30) * 会议 C: [10:00, 11:00) * 会议 D: [11:00, 12:00) 最优解是选择会议 A 和会议 C 或会议 A 和会议 D。 == 可视化示例 == 以下是一个区间调度的 Mermaid 图示: <mermaid> gantt title 区间调度示例 dateFormat HH:mm axisFormat %H:%M section 区间 A :a1, 09:00, 10:00 B :a2, 09:30, 10:30 C :a3, 10:00, 11:00 D :a4, 11:00, 12:00 </mermaid> == 变种问题 == 区间调度问题有多种变体,例如: 1. '''加权区间调度''':每个区间有权重,目标是最大化总权重。 2. '''多资源调度''':有多个资源(如多个会议室),如何安排最多的区间。 3. '''区间着色''':用最少的颜色给区间着色,使得重叠区间颜色不同。 == 总结 == 区间调度问题是贪心算法的典型应用,通过选择'''最早结束的区间'''可以高效地找到最优解。该问题在任务调度、资源分配等领域有重要应用。初学者可以通过代码实现和示例加深理解,而高级用户可以进一步探索其变种问题。 [[Category:计算机科学]] [[Category:数据结构与算法]] [[Category:贪心算法]]
摘要:
请注意,所有对代码酷的贡献均被视为依照知识共享署名-非商业性使用-相同方式共享发表(详情请见
代码酷:著作权
)。如果您不希望您的文字作品被随意编辑和分发传播,请不要在此提交。
您同时也向我们承诺,您提交的内容为您自己所创作,或是复制自公共领域或类似自由来源。
未经许可,请勿提交受著作权保护的作品!
取消
编辑帮助
(在新窗口中打开)