435. 无重叠区间

古城微笑少年丶 2024-04-01 10:40 65阅读 0赞

问题描述：给定一个区间的集合 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;
        }

![在这里插入图片描述][68224f9684be42239509d9169794166f.png]

[68224f9684be42239509d9169794166f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c1114bf270a842af9c14ef7960a09f6b.png