- 正确答案：最少删除的区间数等于总区间数减去最多能保留的不相交区间的数量。可以通过贪心算法求出最多不相交区间数，从而得到最少需要删除的区间个数。 - 解答思路： 1. 将问题转化为“最多能保留多少个互不重叠的区间”，这是一个经典的区间调度问题（Activity Selection Problem）。 2. 使用贪心策略：按照每个区间的右端点（即结束位置）从小到大排序。 3. 遍历排序后的区间列表，每次选择当前可选区间中结束最早的且与上一个已选区间不重叠的区间。 4. 统计最多可以选择多少个不相交区间，记为 keep。 5. 最少删除的区间数 = 总区间数 n - keep。例如：输入区间：[[1,3], [2,4], [3,6]] 排序后：[[1,3], [2,4], [3,6]]（按右端点排序）选择过程： - 选 [1,3] - 下一个 [2,4] 与 [1,3] 相交（3 >= 2），跳过 - [3,6] 与 [1,3] 不相交（3 <= 3，注意闭区间端点相等也算不相交），可以选但实际 [1,3] 和 [3,6] 在 x=3 处有公共点，在闭区间下是否算相交？关键点在此！澄清：题目是“闭区间”，两个区间 [a,b] 和 [c,d] 如果满足 b < c 或 d < a 则不相交；否则相交。特别地，[1,3] 和 [3,6] 在 x=3 处有交集，因此它们是相交的！所以不能同时保留。修正判断条件：两个闭区间 [a,b] 和 [c,d] 不相交当且仅当 b < c 或 d < a。等价于 max(a,c) > min(b,d) 时不相交？不对。正确判断：相交的充要条件是 max(a,c) <= min(b,d) 所以不相交的条件是：b < c 或 d < a 因此 [1,3] 和 [3,6]：max(1,3)=3，min(3,6)=3 → 3<=3 → 相交。所以不能共存。所以在贪心选择时，必须保证下一个区间的左端点 > 上一个区间的右端点（严格大于），才能不相交。因此算法步骤： 1. 按右端点升序排序 2. 初始化 last_end = 负无穷 3. 遍历每个区间 [start, end]： if start > last_end: 选择该区间 last_end = end 4. 记录选择的区间数量 keep 5. 删除数量 = n - keep - 深度知识讲解：这个问题的核心考点是： 1. 区间调度问题的经典贪心解法 2. 贪心策略的正确性证明（交换论证法） 3. 排序在优化搜索顺序中的作用 4. 闭区间边界处理的细节（容易出错）底层数据结构：数组或列表存储区间，排序使用快速排序或归并排序（O(n log n)）为什么按右端点排序是正确的？直观理解：尽早结束的区间给后续留下更多空间。数学上可用反证法或交换论证证明：假设存在最优解不包含最早结束的某个兼容区间，则可通过替换使其仍为最优解，从而说明贪心选择安全。时间复杂度：O(n log n)，主要开销在排序；遍历 O(n) 空间复杂度：O(1)（若原地排序）扩展场景： - 若区间有权重（如会议价值不同），则不能用贪心，需动态规划（加二分优化可达 O(n log n)） - 多机调度问题（多个资源并行执行任务）可用贪心+优先队列解决相关变种题： - 合并重叠区间 - 插入新区间后合并 - 判断是否有重叠区间 - 区间覆盖问题（用最少区间覆盖一段范围）代码示例（Python风格伪代码）： ``` def eraseOverlapIntervals(intervals): if not intervals: return 0 # 按右端点升序排序 intervals.sort(key=lambda x: x[1]) keep = 0 last_end = float('-inf') # 上一个被保留区间的右端点 for interval in intervals: start, end = interval[0], interval[1] if start > last_end: # 当前区间与上一个保留的不相交 keep += 1 last_end = end # 更新最后结束时间 return len(intervals) - keep ``` 测试用例验证：输入：[[1,2], [2,3], [3,4], [1,3]] 排序后：[[1,2], [2,3], [3,4], [1,3]]（按右端点）选择： [1,2]: 1 > -inf → 选，last_end=2 [2,3]: 2 > 2? 否（2==2，但要求严格大于）→ 不选 [3,4]: 3 > 2 → 选，last_end=4 [1,3]: 已排序靠后，但不会影响前面的选择 keep = 2，删除 = 4 - 2 = 2 但其实最优可以保留 [1,2] 和 [3,4]，或 [2,3] 和 [3,4]？不行，[2,3] 和 [3,4] 在3处相交。实际上只能保留两个不相交区间，确实最少删2个。另一个例子：[[1,100], [11,22], [1,11], [2,12]] 按右端点排序：[1,11], [2,12], [11,22], [1,100] 选择： [1,11] → last_end=11 [2,12]: 2 <= 11 → 跳过 [11,22]: 11 <= 11 → 跳过（因为11不大于11） [1,100]: 跳过只保留1个，删除3个。但实际上可以保留 [1,11] 和 [11,22]？不行，它们在11处相交。或者 [2,12] 和 [11,22]？2~12 和 11~22 在[11,12]重叠。唯一可能的是 [1,11] 和 [11,22] 不行，都相交。但 [11,22] 单独 + [1,11] 前面那个？还是不行。其实最大不相交集合大小为2吗？比如 [1,11] 和 [11,22] 不行。等等，发现 [1,11] 和 [11,22] 相交于11，所以不行。那有没有办法取两个？[2,12] 和 [11,22] 明显相交。 [1,11] 和 [2,12] 相交。看来只能取一个？不对，[11,22] 是独立的，但它左边最小右端点是11。但如果先选 [1,11]，后面都无法选。如果选 [11,22]，前面 [1,11] 的右端点更小，应该优先选更早结束的。贪心策略正是如此：选最早结束的，即 [1,11]，然后后面都不能选。所以最多保留1个，删3个。但如果有一个区间 [12,13]，它就能和 [1,11] 兼容。总结：本题的关键在于正确定义“不相交”（闭区间端点接触视为相交），并采用“按结束时间排序 + 贪心选择”的经典方法。这是面试中高频出现的区间类问题，考察候选人对贪心算法的理解和边界处理能力。

小红书商业技术 一面 9.19

全站热榜

创作者周榜

小红书商业技术一面 9.19