91、★贪心-二维-类似于90的力扣452题-LeetCode-435.无重叠区间

题目描述：

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

来源：力扣（LeetCode）

思路：

1）二维数组的排序：要考虑 0 的情况，返回值为什么！

避免溢出：

        Arrays.sort(intervals,new Comparator(){
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] < o2[1]) return -1;
                else if(o1[1] == o2[1]) return 0;
                else return 1;
                //两列都是从小到大排列
            }
        });

不考虑溢出问题：

        Arrays.sort(intervals, new Comparator() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1] - interval2[1];
            }
        });

代码：

1）排序 + 贪心

class Solution {
   public int eraseOverlapIntervals(int[][] intervals) {
        int res = 0;
        //按头部位置，从小到大排序
        Arrays.sort(intervals,new Comparator(){
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] < o2[1]) return -1;
                else if(o1[1] == o2[1]) return 0;
                else return 1;
                //两列都是从小到大排列
            }
        });
        for(int i = 0;i < intervals.length;i++){
            int temp = intervals[i][1];//拿到当前的尾部
            i++;
            while(i < intervals.length && intervals[i][0] < temp){
                res++;
                i++;
            }
            i--;
        }
        return res;
    }
}