435. 无重叠区间

435. 无重叠区间

题目：
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

将整个重叠区间看做一个整体且计数
按照题意画分析图：

1. 画分析图时应罗列出所有情况
2. 至少有三个点才能模拟出几乎所有的可能情况
3. 注意起点情况，终点情况，中间点情况

题解：
有很多区间重叠你需要移除恰当的区间（怎么恰当呢，看起来就复杂），我们不妨想一想应该留下哪些区间，那么与这个区间重叠的就是应该丢弃的区间。

重叠区间的基准（即与哪一个区间为重复判断这个为重叠区间）即保留什么区间——当然是左边没有元素的区间右边是否有元素可以不管。当左边有元素右边有元素那么这个区间就要删掉。

找到做题关键点、突破点。
代码：

class Solution {
    
public:
    // 按照区间右边界排序
    static bool cmp (const vector<int>& a, const vector<int>& b) {
    
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);

        int result = 1; // points 不为空至少需要一支箭
        for (int i = 1; i < intervals.size(); i++) {
    
            if (intervals[i][0] >= intervals[i - 1][1]) {
    
                result++; // 需要一支箭
            }
            else {
      // 气球i和气球i-1挨着
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重叠气球最小右边界
            }
        }
        return intervals.size() - result;
    }
};