题目描述
思路解析动画文字版
记住三件事：按右端排序、prevEnd 记上一个保留区间的右端、start ≥ prevEnd 就保留否则删。下面一步步演。
先看原始的 8 个区间：[1,3] [2,4] [3,5] [1,2] [4,6] [5,7] [6,8] [5,6]。直接处理不好下手，先按每个区间的右端从小到大排个序。
排好序后变成 [1,2] [1,3] [2,4] [3,5] [4,6] [5,6] [5,7] [6,8]。下面每个格子里的数字，就是对应区间的右端 end，从左到右递增。
开始处理前：还没保留任何区间，prevEnd 当成无穷小，删除数 = 0。从最左边（右端最小）的区间开始扫。
指针走到第 0 个区间 [1,2]，它的左端是 1。拿这个左端去和 prevEnd（无穷小）比，决定保留还是删。
左端 1 不小于 prevEnd，说明它和前面保留的区间不重叠 → 保留（标绿）。prevEnd 更新成它的右端 2。
指针走到第 1 个区间 [1,3]，它的左端是 1。拿这个左端去和 prevEnd（2）比，决定保留还是删。
左端 1 比 prevEnd（2）小，说明它和前一个保留的区间重叠了 → 删掉（标红）。删除数加一变成 1，prevEnd 不动。
指针走到第 2 个区间 [2,4]，它的左端是 2。拿这个左端去和 prevEnd（2）比，决定保留还是删。
左端 2 不小于 prevEnd，说明它和前面保留的区间不重叠 → 保留（标绿）。prevEnd 更新成它的右端 4。
指针走到第 3 个区间 [3,5]，它的左端是 3。拿这个左端去和 prevEnd（4）比，决定保留还是删。
左端 3 比 prevEnd（4）小，说明它和前一个保留的区间重叠了 → 删掉（标红）。删除数加一变成 2，prevEnd 不动。
指针走到第 4 个区间 [4,6]，它的左端是 4。拿这个左端去和 prevEnd（4）比，决定保留还是删。
左端 4 不小于 prevEnd，说明它和前面保留的区间不重叠 → 保留（标绿）。prevEnd 更新成它的右端 6。
指针走到第 5 个区间 [5,6]，它的左端是 5。拿这个左端去和 prevEnd（6）比，决定保留还是删。
左端 5 比 prevEnd（6）小，说明它和前一个保留的区间重叠了 → 删掉（标红）。删除数加一变成 3，prevEnd 不动。
指针走到第 6 个区间 [5,7]，它的左端是 5。拿这个左端去和 prevEnd（6）比，决定保留还是删。
左端 5 比 prevEnd（6）小，说明它和前一个保留的区间重叠了 → 删掉（标红）。删除数加一变成 4，prevEnd 不动。
指针走到第 7 个区间 [6,8]，它的左端是 6。拿这个左端去和 prevEnd（6）比，决定保留还是删。
左端 6 不小于 prevEnd，说明它和前面保留的区间不重叠 → 保留（标绿）。prevEnd 更新成它的右端 8。
全部扫完。绿色是保留下来互不重叠的 4 个区间，红色是被删的 4 个。最少删除数 = 4，就是答案。
三个高频追问：prevEnd 的含义与初值、端点相接不算重叠、以及和活动选择问题的关系。
参考代码
def eraseOverlapIntervals(intervals): intervals.sort(key=lambda x: x[1]) # 按右端排序 prev_end = float('-inf') # 上个保留区间的右端 removed = 0 for s, e in intervals: if s >= prev_end: # 不重叠：保留 prev_end = e else: # 重叠：删掉 removed += 1 return removed复杂度
- 时间：O(n log n)，主要花在按右端排序上；之后只线性扫一遍
- 空间：O(1)，除排序外只用 prevEnd 和删除数两个变量（不计排序自身开销）
易错点
面试追问把动画讲成自己的话
追问prevEnd 代表什么？为什么初始设成无穷小？
追问区间端点相接，比如 [1,2] 和 [2,3]，算重叠吗？
追问这题和「最多不重叠区间数 / 活动选择」是什么关系？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
会议室
LeetCode 252 · 简单 · 沿着 区间 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题