435. 无重叠区间
题目描述
输入区间数组 intervals，其中 intervals[i] = [start_i, end_i]。
从中删掉一些区间，让剩下的任意两个区间都没有重叠。返回最少需要删掉几个。
两个区间如果只在一个端点处相碰（例如 [1,2] 和 [2,3]），不算重叠。
示例 1
输入：intervals = [[1,2],[2,3],[3,4],[1,3]] 输出：1
解释：删去 [1,3] 后，其余区间两两只在端点相碰。
示例 2
输入：intervals = [[1,2],[1,2],[1,2]] 输出：2
解释：三个 [1,2] 相互重叠，只能留一个，删掉 2 个。
示例 3
输入：intervals = [[1,2],[2,3]] 输出：0
解释：两个区间只在 2 处相碰，不需要删。
数据范围
1 <= intervals.length <= 10^5intervals[i].length == 2-5 * 10^4 <= start_i < end_i <= 5 * 10^4
解题思路：按右端点贪心
最少移除 = 总数 - 最多能保留的不重叠区间数。按右端点从小到大排序，依次扫描：如果左端点不小于上一个保留区间的右端 end，就保留它并更新 end。优先保留结束得早的区间，给后面留下的空间最多，交换论证可证明这样不会变差。
为什么正确
已保留的区间互不重叠，且在所有“同样保留 keep 个”的方案中，最后一个右端 end 最小。
复杂度分析
时间 O(n log n)（排序），额外空间 O(log n)。
易错点
按左端点排序后直接贪心会出错（一个很长的区间可能最先被保留）。另外判断用 s >= end，端点相接不算重叠。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1])
end = -math.inf
keep = 0
for s, e in intervals:
if s >= end:
keep += 1
end = e
return len(intervals) - keepclass 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[] it : intervals) {
if (it[0] >= end) {
keep += 1;
end = it[1];
}
}
return intervals.length - keep;
}
}class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
long long end = LLONG_MIN;
int keep = 0;
for (auto& it : intervals) {
if (it[0] >= end) {
keep += 1;
end = it[1];
}
}
return intervals.size() - keep;
}
};func eraseOverlapIntervals(intervals [][]int) int {
sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
end := math.MinInt64
keep := 0
for _, it := range intervals {
if it[0] >= end {
keep += 1
end = it[1]
}
}
return len(intervals) - keep
}var eraseOverlapIntervals = function(intervals) {
intervals.sort((a, b) => a[1] - b[1]);
let end = -Infinity;
let keep = 0;
for (const [s, e] of intervals) {
if (s >= end) {
keep += 1;
end = e;
}
}
return intervals.length - keep;
};function eraseOverlapIntervals(intervals: number[][]): number {
intervals.sort((a, b) => a[1] - b[1]);
let end = -Infinity;
let keep = 0;
for (const [s, e] of intervals) {
if (s >= end) {
keep += 1;
end = e;
}
}
return intervals.length - keep;
}其他解法
贪心与动态规划复杂度相同；贪心更短且省空间，动态规划更通用，区间带权时仍然适用。
解法 2：动态规划 + 二分查找 时间 O(n log n)，空间 O(n)
按右端点排序。dp[i] 表示只看前 i 个区间时最多能保留几个互不重叠的区间。对第 i 个区间，二分找出右端点不超过它左端点的区间个数 j。转移为 dp[i+1] = max(dp[i], dp[j] + 1)。答案是 n - dp[n]。
不需要证明贪心正确性，思路可以推广到带权区间调度。需要 O(n) 的 dp 数组，代码比贪心长。
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1])
n = len(intervals)
ends = [e for _, e in intervals]
# dp[i]：只看前 i 个区间（按右端点排序）时最多保留几个
dp = [0] * (n + 1)
for i, (s, e) in enumerate(intervals):
j = bisect_right(ends, s, 0, i)
dp[i + 1] = max(dp[i], dp[j] + 1)
return n - dp[n]class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int n = intervals.length;
int[] dp = new int[n + 1];
for (int i = 0; i < n; i++) {
int s = intervals[i][0];
int lo = 0, hi = i;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (intervals[mid][1] <= s) lo = mid + 1;
else hi = mid;
}
dp[i + 1] = Math.max(dp[i], dp[lo] + 1);
}
return n - dp[n];
}
}class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
int n = intervals.size();
vector<int> ends(n), dp(n + 1, 0);
for (int i = 0; i < n; i++) ends[i] = intervals[i][1];
for (int i = 0; i < n; i++) {
int j = upper_bound(ends.begin(), ends.begin() + i, intervals[i][0]) - ends.begin();
dp[i + 1] = max(dp[i], dp[j] + 1);
}
return n - dp[n];
}
};func eraseOverlapIntervals(intervals [][]int) int {
sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
n := len(intervals)
dp := make([]int, n+1)
for i := 0; i < n; i++ {
s := intervals[i][0]
lo, hi := 0, i
for lo < hi {
mid := (lo + hi) / 2
if intervals[mid][1] <= s {
lo = mid + 1
} else {
hi = mid
}
}
dp[i+1] = dp[i]
if dp[lo]+1 > dp[i+1] {
dp[i+1] = dp[lo] + 1
}
}
return n - dp[n]
}var eraseOverlapIntervals = function(intervals) {
intervals.sort((a, b) => a[1] - b[1]);
const n = intervals.length;
const dp = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
const s = intervals[i][0];
let lo = 0, hi = i;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (intervals[mid][1] <= s) lo = mid + 1;
else hi = mid;
}
dp[i + 1] = Math.max(dp[i], dp[lo] + 1);
}
return n - dp[n];
};function eraseOverlapIntervals(intervals: number[][]): number {
intervals.sort((a, b) => a[1] - b[1]);
const n = intervals.length;
const dp: number[] = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
const s = intervals[i][0];
let lo = 0, hi = i;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (intervals[mid][1] <= s) lo = mid + 1;
else hi = mid;
}
dp[i + 1] = Math.max(dp[i], dp[lo] + 1);
}
return n - dp[n];
}