435.无重叠区间.md

这道题首先进行思想转换，题目是让求最少去除多少个区间能够让剩下的区间不重复，那么就转换为求最多可以有多少个不重叠区间，再让所有的区间数目去减。

方法一：动态规划

dp[j] 是以区间 [left_j, right_j] 为结尾的最后一个相互不重叠区间的最大区间数。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            } 
        });
        int[] dp = new int[intervals.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < intervals.length; 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 intervals.length - Arrays.stream(dp).max().getAsInt();
    }
}

方法二：贪心

将intervals数组按照右端点从小到大排序，因为右端点结束的越早就越能给后面的区间留下空间，可能性就越多。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1] - interval2[1];
            } 
        });
        int ans = 1, right = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= right) {
                ans++;
                right = intervals[i][1];
            }
        }
        return intervals.length - ans;
    }
}