---

[!info] related notes 算法面试题型 MOC 贪心算法

无重叠区间

题目

435. 无重叠区间 - 力扣（LeetCode）

题解

改为计算最多可以选多少个互不重叠的区间，那么没选的区间就是要移除的区间。

考虑所选区间中，最左边的那个区间。

最左边的区间选哪个？ 我们可以选所有区间中右端点最小的区间（记作 A）。为什么？因为在任意一种选法中，都可以把最左边的区间，替换成 A。由于 A 是一个更靠左的区间，所以 A 不会与其他已选区间相交，所以这个替换操作是合法的。

所以，在所有最优选法中，一定存在一种选法，选择了右端点最小的区间 A。

去掉区间 A 以及与 A 相交的区间（这些区间的左端点都小于 A 的右端点），问题变成：

剩余区间中最多可以选多少个互不重叠的区间？ 这是一个规模更小的子问题，可以用递归/迭代解决。

var eraseOverlapIntervals = function(intervals) {
    intervals = intervals.sort((a,b) => a[1] - b[1]);
    let ans = 0;
    let preR = -Infinity;
    for (const [l,r] of intervals) {
        if (l >= preR) {
            ans++;
            preR = r;
        }
    }
    return intervals.length - ans;
};

参考