按最早结束时间选择活动
安排数量最多且互不重叠的事件
按最早结束时间选择活动 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
调度问题
给定带有开始和结束时间的活动，活动选择问题要求您在任意两个活动都不重叠的情况下，参加尽可能多的活动。📅
重叠意味着冲突
如果一个活动在另一个活动结束之前开始，那么两项活动就会冲突。对于任意一对重叠的活动，您只能选择其中一个。
取胜规则
贪心的关键是：在所有仍可选择的活动中，始终选择最早结束的那一个。越早结束，就能为其他活动留下越多空间。
按结束时间排序
先按结束时间对所有活动进行排序。这样，下一步的最佳选择就是顺序中下一个符合条件的活动。
events.sort(key=lambda e: e[1])记录上一次结束时间
使用一个变量记录上一次选中活动的结束时间。任何新活动都必须在这个时间点或之后开始，才能与已有安排兼容。
last_end = -1遍历并选择
遍历一次已排序的列表。如果某项活动的开始时间不早于上一次的结束时间，就选择它，并将上一次的结束时间更新为该活动的结束时间。
for s, f in events:
if s >= last_end:
count += 1
last_end = f运行时间为 n log n
主要开销来自排序，复杂度为 O(n log n)，之后只需进行一次线性遍历。即使输入规模非常大，这也足够快。
为何最早结束是最佳选择
最先结束的活动会最早释放时间线上的空间，因此绝不会阻碍更好的方案。将它替换进任意最优安排后，结果仍然同样好。
最早开始并不奏效
按照最早开始时间选择，可能会选中一个持续很久、占满全天的活动。仅看持续时间也会误导您，因此应当依据结束时间。
处理边界相接的情况
请明确规定：一个活动恰好在另一个活动开始时结束，是否算作冲突。使用“开始时间 >= 上一次结束时间”即可允许活动首尾相接。
竞赛中的常见形式
许多任务都隐藏着这种模式：预订房间、观看节目或运行作业。识别出它之后，就可以应用最早结束规则。
快速检查
您希望选择数量最多且互不重叠的活动。
回顾
按结束时间对活动排序，然后选择每个开始时间不早于上一次选中活动结束时间的活动。一次排序加一次遍历，就能得到数量最多的活动集合。🚀
常见问题解答
「按最早结束时间选择活动」课时是免费的吗？
是的 — 「按最早结束时间选择活动」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「按最早结束时间选择活动」这节课中我会学到什么？
安排数量最多且互不重叠的事件 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「按最早结束时间选择活动」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 贪心思维
- 按最早结束时间选择活动
- 按比例解决分数背包问题
- 发现贪心法何时会失败