LeetCode 435中等区间 · 贪心
无重叠区间 图解题解
这道题到底在问什么
给定若干区间 intervals[i] = [start, end]，求需要移除的最少区间数，使剩下的区间两两不重叠。
- 输入
- intervals = [[1,3],[2,4],[3,5],[1,2],[4,6],[5,7],[6,8],[5,6]]
- 输出
- 4（删 4 个，剩下 4 个不重叠）
最优解：一步一步想明白
- 3记住三件事：按右端排序、prevEnd 记上一个保留区间的右端、start ≥ prevEnd 就保留否则删。下面一步步演。
- 4先看原始的 8 个区间：[1,3] [2,4] [3,5] [1,2] [4,6] [5,7] [6,8] [5,6]。直接处理不好下手，先按每个区间的右端从小到大排个序。
- 5排好序后变成 [1,2] [1,3] [2,4] [3,5] [4,6] [5,6] [5,7] [6,8]。下面每个格子里的数字，就是对应区间的右端 end，从左到右递增。
- 6开始处理前：还没保留任何区间，prevEnd 当成无穷小，删除数 = 0。从最左边（右端最小）的区间开始扫。
- 7指针走到第 0 个区间 [1,2]，它的左端是 1。拿这个左端去和 prevEnd（无穷小）比，决定保留还是删。
- 8左端 1 不小于 prevEnd，说明它和前面保留的区间不重叠 → 保留（标绿）。prevEnd 更新成它的右端 2。
- 9指针走到第 1 个区间 [1,3]，它的左端是 1。拿这个左端去和 prevEnd（2）比，决定保留还是删。
- 10左端 1 比 prevEnd（2）小，说明它和前一个保留的区间重叠了 → 删掉（标红）。删除数加一变成 1，prevEnd 不动。
- 11指针走到第 2 个区间 [2,4]，它的左端是 2。拿这个左端去和 prevEnd（2）比，决定保留还是删。
- 12左端 2 不小于 prevEnd，说明它和前面保留的区间不重叠 → 保留（标绿）。prevEnd 更新成它的右端 4。
- 13指针走到第 3 个区间 [3,5]，它的左端是 3。拿这个左端去和 prevEnd（4）比，决定保留还是删。
- 14左端 3 比 prevEnd（4）小，说明它和前一个保留的区间重叠了 → 删掉（标红）。删除数加一变成 2，prevEnd 不动。
- 15指针走到第 4 个区间 [4,6]，它的左端是 4。拿这个左端去和 prevEnd（4）比，决定保留还是删。
- 16左端 4 不小于 prevEnd，说明它和前面保留的区间不重叠 → 保留（标绿）。prevEnd 更新成它的右端 6。
- 17指针走到第 5 个区间 [5,6]，它的左端是 5。拿这个左端去和 prevEnd（6）比，决定保留还是删。
- 18左端 5 比 prevEnd（6）小，说明它和前一个保留的区间重叠了 → 删掉（标红）。删除数加一变成 3，prevEnd 不动。
- 19指针走到第 6 个区间 [5,7]，它的左端是 5。拿这个左端去和 prevEnd（6）比，决定保留还是删。
- 20左端 5 比 prevEnd（6）小，说明它和前一个保留的区间重叠了 → 删掉（标红）。删除数加一变成 4，prevEnd 不动。
- 21指针走到第 7 个区间 [6,8]，它的左端是 6。拿这个左端去和 prevEnd（6）比，决定保留还是删。
- 22左端 6 不小于 prevEnd，说明它和前面保留的区间不重叠 → 保留（标绿）。prevEnd 更新成它的右端 8。
- 23全部扫完。绿色是保留下来互不重叠的 4 个区间，红色是被删的 4 个。最少删除数 = 4，就是答案。
⚠️ 容易写错的地方
✗ 错：按左端 start 排序
✓ 对：按右端 end 排序
按右端排，保留的区间右端尽量靠左，给后面腾出最多空间，才能留下最多区间
✗ 错：把 start == prevEnd 当成重叠删掉
✓ 对：start ≥ prevEnd 就算不重叠、保留
区间端点相接（如 [1,2] 和 [2,3]）不算重叠，用 ≥ 而不是 >
✗ 错：去数保留了几个当答案
✓ 对：答案是删掉的个数 removed
题目问的是最少移除数，不是最多保留数；别把两者搞反
完整代码（Python / C++ / Java）
Python
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 removedC++
int eraseOverlapIntervals(vector<vector<int>>& iv){
sort(iv.begin(), iv.end(),
[](auto&a, auto&b){ return a[1] < b[1]; });
long prevEnd = LONG_MIN; int removed = 0;
for (auto& it : iv) {
if (it[0] >= prevEnd) prevEnd = it[1];
else removed++;
}
return removed;
}Java
public int eraseOverlapIntervals(int[][] iv) {
Arrays.sort(iv, (a, b) -> a[1] - b[1]);
long prevEnd = Long.MIN_VALUE; int removed = 0;
for (int[] it : iv) {
if (it[0] >= prevEnd) prevEnd = it[1];
else removed++;
}
return removed;
}复杂度
时间
O(n log n)
主要花在按右端排序上；之后只线性扫一遍
空间
O(1)
除排序外只用 prevEnd 和删除数两个变量（不计排序自身开销）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 无重叠区间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
prevEnd 代表什么？为什么初始设成无穷小？+
prevEnd 是「上一个被保留区间的右端」。初始设成无穷小，是为了让第一个区间的 start 一定 ≥ prevEnd，从而无条件保留第一个区间。
区间端点相接，比如 [1,2] 和 [2,3]，算重叠吗？+
不算。它们只在端点 2 处相接，没有公共内部。判断时用 start ≥ prevEnd（取等号也保留）。
这题和「最多不重叠区间数 / 活动选择」是什么关系？+
是同一个贪心。保留的最多不重叠区间数 = n − 本题答案。活动选择问能安排多少活动，本题问要删几个，互为补数。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 无重叠区间 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。