使用扫描线求最大重叠数
根据事件统计同时存在的区间
使用扫描线求最大重叠数 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
最大重叠问题
有多少个区间同时覆盖同一时刻？峰值数量就是最大重叠数，也就是时间线中最繁忙的时刻。📈
从事件角度思考
不要再把区间作为整体来思考。将每个区间拆成两个事件：开始时增加 +1，结束时减少 -1。
构建事件列表
为每个区间添加一个开始事件和一个结束事件，放入同一个共享列表。每个事件都包含一个位置，以及加一或减一的增量。
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))为事件排序
按位置为所有事件排序，这样您就可以从左到右扫描时间线，并按正确顺序处理变化。
events.sort()扫描并计数
遍历排好序的事件，同时维护一个不断变化的计数器。经过每个事件时加上它的增量，计数器就表示当前有多少个区间处于活动状态。
active = 0
for pos, delta in events:
active += delta跟踪峰值
每次更新后，将计数器与目前的最佳值进行比较。计数器曾达到的最大值就是最大重叠数。
best = max(best, active)打破平局的技巧
位置相同时，顺序很重要。如果位置 x 处的结束应该先释放位置，再处理位置 x 处的开始，就应当让同一点的结束事件排在开始事件之前。
编码增量以实现正确排序
一种巧妙的平局处理方法是选择合适的增量，让元组排序自动完成这件事。位置相同时，将 -1 增量排在 +1 之前。
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tie为什么这么快
您需要创建 2n 个事件，排序一次，再扫描一次。整个方法的时间复杂度为 O(n log n)，主要耗时来自这一次排序。
应用场景
最大重叠可以解决许多经典问题，例如会议所需的最少房间数，或服务器上的同时在线用户峰值。
不只是计数
同样的扫描方法还可以轻松扩展：跟踪总覆盖长度，或者找出所有计数发生变化的位置，而且都只需一次线性扫描。
快速检查
您可以通过扫描事件来寻找最大重叠数。
回顾
将区间转换为 +1 的开始事件和 -1 的结束事件，为它们排序，再扫描计数器以找出峰值。通过让结束事件排在开始事件之前来处理平局。🚀
常见问题解答
「使用扫描线求最大重叠数」课时是免费的吗？
是的 — 「使用扫描线求最大重叠数」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「使用扫描线求最大重叠数」这节课中我会学到什么？
根据事件统计同时存在的区间 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「使用扫描线求最大重叠数」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 按起点排序区间
- 合并重叠区间
- 使用扫描线求最大重叠数
- 使区间互不重叠所需的最少删除数