435. 无重叠区间-蒲公英云

435. 无重叠区间

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

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3]后，剩下的区间没有重叠。

问题思路：

方法一：直接动态规划。

现将二维数据按照右端点进行排序，然后维护dp数组
dp[i]: 到第i个区间时，最大的无重叠区间个数。
dp[i]=max{dp[j]}+1, i > j且intervals[j][1] < intervals[i][0]

public int eraseOverlapIntervals2(int[][] intervals) {
        //用于实现状态转移的dp数组
        int[] dp = new int[intervals.length];
        // 将二维数组按照右端点升序排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        // 按二维数组的区间状态化，dp[i]=max{dp[j]}+1, i > j且intervals[j][1] < intervals[i][0]
        for (int i = 0; i < intervals.length; i++) {
            int maxJ = 0;
            for (int j = 0; j < i; j++) {
                if(intervals[j][1] < intervals[i][0]){
                    maxJ = Math.max(maxJ,dp[j]);
                }
            }
            dp[i] = maxJ + 1;
        }
        return intervals.length - dp[dp.length-1];
    }

方法二：动态规划+二分查找（参考最长递增子串）

维护一个cell数组，存放右端点。
cell[i]: 当最长无重叠区间个数为i时，存放的最大右端点为cell[i]。
所以cell数组是严格递增的，每次可以通过二分查找去更新对应的cell数组。
找到第一个大于自己的右端点，直接覆盖更新即可。若都比自己小，那就从尾部插入。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 存储当前最长无重叠区间的区间右端点
        int[] cell = new int[intervals.length];
        // 将二维数组按照右端点升序排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        // cell数组的长度
        int mode = 1;
        // 先把最先结束的节点存入
        cell[0] = intervals[0][1];
        /**
         * 按二维数组的区间状态化，dp[i]=max{dp[j]}+1, i > j且intervals[j][1] < intervals[i][0]
         * 从第二个元素开始插入比较
         */
        for (int i = 1; i < intervals.length; i++) {
            // 如果和最后一个区间不重叠，且大于最后一个区间，则直接放在最后
            if(intervals[i][1] > cell[mode-1] && intervals[i][0] >= cell[mode-1]){
                cell[mode++] = intervals[i][1];
                continue;
            }
            int left = 0;
            int right = cell.length-1;
            // 二分查找找到第一个大于该节点右端点的cell元素，并覆盖。若没有则直接放在最后
            while(left<right){
                int mid = (left+right)/2;
                if(intervals[i][1] > cell[mid]){
                    right = mid;
                }else{
                    left = mid+1;
                }
            }
            // 第一个大的数肯定存在left,同时该区间的左节点大于前一个数据的右端点
            if(left>0 && intervals[i][0] >= cell[left-1]){
                cell[left] = intervals[i][1];
            }
        }
        return intervals.length-mode;
    }
}

方法三：动态规划+贪心

先将数组按右端点排序，区间想像成会议时间，第一个区间即相当于第一个结束的会议，往后去遍历，从最先的结束时间会议中，找到第一个不和第一个会议重叠的区间，然后依次如此判断。

public int eraseOverlapIntervals(int[][] intervals) {
        // 将二维数组按照右端点升序排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        // 存储当前最长无重叠区间的区间右端点
        int max = intervals[0][1];
        int size = 1;
        /**
         * 贪心策略，当前i元素，左端点大于前一位，右端点小于目前尾数，则覆盖
         * 从第二个元素开始插入比较
         */
        for (int i = 1; i < intervals.length; i++) {
            // 如果该元素
            if(intervals[i][0] >= max){
                max = intervals[i][1];
                size++;
            }
        }
        return intervals.length-size;
    }