class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n=intervals.length;
        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] intervals1,int[] intervals2){
                return intervals1[0]-intervals2[0];
            }
        });
        int[] dp=new int[n];
        Arrays.fill(dp,1);
        for(int i=1;i<n;i++){
        	//遍历前面的区间
            for(int j=0;j<i;j++){
                //无重叠
                if(intervals[j][1]<=intervals[i][0])
                    dp[i]=Math.max(dp[i],dp[j]+1);
            }
        }
        return n-Arrays.stream(dp).max().getAsInt();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$

很坑的是，这题动态规划过不了，会超时…还以为是我写的有问题，结果官解也超时…

贪心

关于为什么是按照区间右端点排序？
按照右端点排序，我们一定能够找到一个最先结束的会议，给后面会议预留更长时间，如下图，选a的话只能ad，但如果选b的话可以bcd，移除一个区间即可。

|_________|                  区间a
  |___|                      区间b       
       |__|                  区间c   
            |______|         区间d   
1
2
3
4

那么本题的贪心策略就是，将区间按照右端点排序，如果当前遍历到的区间 $[l_i,r_i]$与上一个区间不重合，即 $l_i\ge right$，那么我们就可以贪心地选择这个区间，并将 right 更新为 $r_i$

这道题画一个区间图就很好理解了

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n=intervals.length;
        //区间按照右端点排序
        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] intervals1,int[] intervals2){
                return intervals1[1]-intervals2[1];
            }
        });
        int res=1;//剩余的不重叠区间
        int right=intervals[0][1];//当前最右端点位置
        for(int i=1;i<n;i++){
        	//区间不重叠
            if(intervals[i][0]>=right){
                res++;
                right=intervals[i][1];//更新最右端点位置
            }
        }
        return n-res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度：$O(nlogn)$

空间复杂度：$O(logn)$

↑均为排序所需的复杂度