0Pricing
Competitive Programming Academy · 课时

使区间互不重叠所需的最少删除数

按最早结束时间贪心保留区间

使区间互不重叠所需的最少删除数 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

删除目标

现在有一些相互重叠的区间，您希望进行最少的删除，使它们不再重叠。请尽可能多地保留区间。✂️

转换问题

删除最少的区间，就等价于保留最多的不重叠区间。先解决保留问题，然后用 n 减去保留的数量，就得到删除次数。

这就是活动选择问题

保留最多的不重叠区间，本质上就是经典的活动选择问题。同一个贪心思路可以解决这两个问题。

按结束时间排序

这里正确的排序依据是结束时间，而不是起点。越早结束，就能越早为可能保留的下一个区间腾出时间线。

intervals.sort(key=lambda x: x[1])

贪心选择

在所有仍然兼容的区间中，始终保留结束时间最早的那个。这样可以为其余区间留下最大的空间。

跟踪上一个保留区间的终点

记录上一个保留区间的终点。下一个区间只有在其起点大于或等于该边界时，才与前面的区间兼容。

if start >= last_end:
    last_end = end

统计删除次数

如果某个区间的起点早于 last_end，就会发生冲突，因此请将其丢弃，并将删除计数加一。否则就保留它。

else:
    removed += 1

为什么选择最早结束

可以通过交换论证来证明：将任意一个已保留区间替换为兼容且结束最早的区间，永远不会减少最终能够保留的区间数量。

处理接触边界

请判断 [1, 2] 和 [2, 3] 是否算作重叠。如果允许仅共享端点的区间共存，就应当使用 start >= last_end 作为判断条件。

完整的贪心方法

按结束时间排序，扫描一次并统计冲突。总时间复杂度为 O(n log n)，其中排序之后只需进行一次线性扫描。

removed = 0; last_end = float('-inf')
for s, e in intervals:
    if s >= last_end: last_end = e
    else: removed += 1

熟悉的结构

这种模式可以安排一个房间中的最多会议，或在一台机器上安排最多任务。只要题目要求最小化冲突，就应当想到它。

快速检查

您会用贪心方法保留互不重叠的区间。

回顾

最少删除次数等于 n 减去最多能够保留的区间数。按结束时间排序，贪心地保留结束最早且兼容的区间，并统计其余区间。🚀

常见问题解答

「使区间互不重叠所需的最少删除数」课时是免费的吗？

是的 — 「使区间互不重叠所需的最少删除数」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「使区间互不重叠所需的最少删除数」这节课中我会学到什么？

按最早结束时间贪心保留区间 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。

「使区间互不重叠所需的最少删除数」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 按起点排序区间
  2. 合并重叠区间
  3. 使用扫描线求最大重叠数
  4. 使区间互不重叠所需的最少删除数
← 返回 Competitive Programming Academy