LeetCode #435：Non-overlapping Intervals(无重叠区间)

题目描述

由于本题只要求 “需要移除区间的最小数量”，所以不需要模拟区间被删除的过程。同时本题如果要直接统计重叠区间也不是很方便，我们将问题转化为先求这些区间中非重叠的区间，再用区间总数减去非重叠区间的个数得到答案。

首先将这些区间按右边界从小到大排序，从左向右遍历 intervals 记录非重叠区间的个数。按右边界排序后，默认第一个区间 [a, b] 为非重叠区间，之后往后寻找第一个满足 b <= c 条件的区间 [c, d] 作为第二个非重叠区间，再往后寻找第一个满足 d <= e 的区间 [e, f] 作为第三个非重叠区间……以此类推直到遍历完所有 intervals。之后将区间总个数减去非重叠区间个数即为要去除的重叠区间个数。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        int n = intervals.size();
        int nums = 1; // 统计独立区间的个数，默认第一个区间为非重叠区间
        int rightMargin = intervals[0][1]; // 记录最新非重叠区间的右边界
        for(int i = 1; i < n; i ++) {
            if(rightMargin <= intervals[i][0]) { // 找到了新的非重叠区间
                nums ++;
                rightMargin = intervals[i][1]; // 更新最新非重叠区间的右边界
            }
        }

        return n - nums;
    }

    static bool cmp(vector<int>& a, vector<int>& b) {
        return a[1] < b[1];
    }
};

本题也可以用 #452 的思路解决，因为箭的数量就是非重叠区间的数量。只不过本题中 [1, 2] 与 [2, 3] 是被视为非重叠区间的，那么我们只需要在 #452 的代码中稍微修改一下即可。

实质上本方法就是将区间按左边界排序后的解法。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        int n = intervals.size();
        int nums = 1;
        for(int i = 1; i < n; i ++) {
            if(intervals[i - 1][1] <= intervals[i][0]) // 改动1：认为[1,2]和[2,3]不是重叠区间
                nums ++;
            else
                intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);
        }

        return n - nums; // 改动2：总区间减去非重叠区间数，返回重叠区间数
    }

    static bool cmp(vector<int>& a, vector<int>& b) {
        return a[0] < b[0];
    }
};