学习目标

• 能把“最少删除”转化为“最多保留”的等价优化目标。
• 使用按结束时间排序的活动选择策略解决区间调度问题。
• 能解释端点接触的边界，并用交换论证说明最早结束选择的正确性。

前置知识

• 二维数据的自定义排序。
• 区间重叠的判断方法。
• 贪心算法的交换论证。

问题描述

给定 n 个区间，每个区间写作 [start, end]，且 start < end。请删除尽可能少的区间，使剩余区间两两不重叠。

如果前一个区间的结束位置等于后一个区间的开始位置，它们只在端点接触，视为不重叠。例如 [1, 2] 与 [2, 3] 可以同时保留。

输入格式

• 第一行输入一个整数 n，表示区间数量。
• 接下来 n 行，每行输入两个整数 start end，表示一个区间。

输出格式

输出一个整数，表示为了使剩余区间互不重叠，最少需要删除的区间数。

约束

• 1 ≤ n ≤ 100000。
• -50000 ≤ start < end ≤ 50000。
• 输入顺序不保证有序，也可能包含完全相同的区间。

示例

示例 1：混合重叠

输入：

4
1 2
2 3
3 4
1 3

输出：

1

示例 2：重复区间

输入：

3
1 2
1 2
1 2

输出：

2

示例 3：端点接触

输入：

2
1 2
2 3

输出：

0

思路提示

最少删除数等于区间总数减去最多可保留数，因此可以先解决“最多选出多少个互不重叠区间”。

把所有区间按结束位置升序排列。每次保留当前最早结束且与上一个已选区间不冲突的区间，并记录它的结束位置。后续区间满足 start ≥ lastEnd 时即可继续保留。

这个选择会给后续区间留下尽可能大的可用范围。若某个最优方案首先选择了结束更晚的区间，可以把它换成当前最早结束的区间；交换后不会排除原本能够接在后面的区间，所以保留数量不会减少。

复杂度分析

• 时间复杂度：O(n log n)，主要来自排序。
• 额外空间复杂度：除输入数组和排序所需空间外，扫描部分为 O(1)。

测试设计提示

公开测试共 20 组，每组 5 分，总分 100 分。测试覆盖三个样例、单区间、无序输入、嵌套与重复区间、相同起点或终点、负坐标、端点接触、坐标边界，以及 n = 100000 的压力数据。

运行与评分

在本 Lab 目录执行：

make doctor
make run
make score

如果没有 Make，也可以在仓库根目录执行：

pnpm lab:run -- labs/chapter-13/exercise/E-13-05-non-overlapping-intervals --target student

参考实现可以使用下面的命令验证：

pnpm lab:verify -- labs/chapter-13/exercise/E-13-05-non-overlapping-intervals --no-color

完成清单

• 正确读取全部区间并按结束位置排序。
• 把最少删除转换为总数减去最多保留数。
• 使用 start ≥ lastEnd 判断端点接触的区间可同时保留。
• 正确处理重复、嵌套、负坐标和大规模输入。
• 20 个公开测试全部通过，严格评分为 100/100。

思考与复盘

1. 为什么按开始位置最早选择不能保证保留区间数最多？
2. 如果端点接触也算重叠，兼容条件应如何修改？
3. 直接统计扫描中发生的冲突，与计算 n - kept 有什么关系？

题目来源

本题对应 LeetCode 435「无重叠区间」：https://leetcode.cn/problems/non-overlapping-intervals/。本 Lab 将二维数组参数改写为标准输入输出格式。