力扣435题（贪心算法，无重叠区间）

452.给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

1. 这个题第一眼看下来就隐隐约约感觉需要先进行排序才可以做，但是又感觉不太需要，觉得遍历一下每个区间然后发现重叠就进行计数就可以了，但是一动手又不知道应该怎么去做，比如如果有三个区间，那么如果第二个区间跟第一个和第三个区间都有相交的话，那么显然我可以去掉第二个区间就不会有重叠区间了，但是按照我前面这种想法的话那就是要去掉两个区间，这肯定是不对的。所以只能带着疑问看看题解。
2. 题解的解法确实是用了排序，但是感觉整体思路跟自己之前的想法还是不太一样，比较巧妙。题解是将这些区间按照右边界进行一个升序排序，然后记录非交叉区间的个数，最后用区间数量减去非交叉区间就得到需要去除的区间数量。
3. 这里所谓的非交叉区间，实际上是这样的。在给所有的区间排好序之后，一开始选定第一个区间的右边界作为分割点，那么往后遍历区间，出现的第一个不与该分割点产生交集的区间就是所谓的非交叉区间，然后将这个区间的右边界作为分割点，再进一步寻找下一个非交叉区间。
4. 这道题目的贪心体现在：
   局部最优：给区间按右区间排序完后，当有重叠区间的时候，优先保留右边界小的区间，尽可能留给下一个区间更大的空间，从而避免重叠。
   全局最优：选取最多的非交叉区间，从而得到最少的去除区间数量。
5. 说实话代码写下来还是比较简单的，但是具体解题的思路还是比较难以理解，需要多加琢磨。
6. 代码如下

int cmp_int(const void* _a, const void* _b) {
    int** a = (int**)_a;
    int** b = (int**)_b;
    return (*a)[1] -  (*b)[1];
}

int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){
    if (intervalsSize == 0)
        return 0;
    // 按照右边界进行升序排序
    qsort(intervals, intervalsSize, sizeof(int) * 2, cmp_int);
    int count = 1; //记录非交叉区间的个数
    int end = intervals[0][1];
    for (int i = 1; i < intervalsSize; i++) {
        if (end <= intervals[i][0]) {
            end = intervals[i][1];
            count++;
        }
    }
    return intervalsSize - count;