LeetCode 435中等区间 · 贪心
无重叠区间 图解题解
这道题到底在问什么
给一组区间，移除最少数量的区间，使剩余区间互不重叠。
- intervals
- [[1,2],[2,3],[3,4],[1,3]]
- 输出
- 1
最优解：一步一步想明白
⚠️ 容易写错的地方
✗ 错：按左端点排序后贪心
✓ 对：按右端点排序
结束早才给后续留下更多空间
✗ 错：把 start == end 当重叠
✓ 对：条件是 start >= end 可保留
区间端点相接不算重叠
完整代码（Python / C++ / Java）
Python
class Solution:
def eraseOverlapIntervals(self, intervals):
intervals.sort(key=lambda x: x[1]) # 按右端 end 排序
end = float("-inf")
keep = 0
for s, e in intervals:
if s >= end: # 不重叠 → 保留
keep += 1
end = e
return len(intervals) - keep # 总数 − 保留 = 删除数C++
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(),
[](auto& a, auto& b){ return a[1] < b[1]; }); // 按右端排
long end = LONG_MIN; int keep = 0;
for (auto& iv : intervals)
if (iv[0] >= end) { keep++; end = iv[1]; } // 不重叠→保留
return intervals.size() - keep;
}
};Java
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); // 按右端排
long end = Long.MIN_VALUE; int keep = 0;
for (int[] iv : intervals)
if (iv[0] >= end) { keep++; end = iv[1]; } // 不重叠→保留
return intervals.length - keep;
}
}套路模板 · 区间调度贪心骨架
# 区间调度贪心 骨架
intervals.sort(key=lambda x: x[1]) # 按右端 end 排序
end = float("-inf")
keep = 0
for s, e in intervals:
if s >= end: # 与上一个保留区间不重叠
keep += 1
end = e
return len(intervals) - keep # 删除数 = 总数 − 保留数复杂度
时间复杂度
O(n log n)
排序区间
空间复杂度
O(1)
只用 keep 和 end
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 无重叠区间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
按区间右端 end 升序排序，贪心地从左到右保留与「上一个保留区间」不重叠(start ≥ end)的区间、更新 end；最少删除数 = 总数 − 保留数。
为什么按右端排序是最优的？+
交换论证：在任意最优解里，把第一个保留区间换成「右端最小」的那个不会变差(它结束更早、不会挡住更多后续区间)。逐步替换即得按右端贪心的最优性。这就是经典的区间调度问题。
复杂度多少？+
排序 O(n log n) 主导，扫描 O(n)，额外空间 O(1)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。