435. 无重叠区间

// LeetCode指定调用方法
public int eraseOverlapIntervals(int[][] intervals) {
		
    // 如果区间为空，则直接返回0
    int count = intervals.length;
    if (count == 0) return 0;

    // 根据区间结尾排序从小到大排序
    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[1] - o2[1];
        }
    });

    // 选择结尾最小，并且和前一个区间不重叠的区间
    int number = 1;
    int index = 0;
    for (int i = 1; i < count; i++) {
        if (intervals[index][1] <= intervals[i][0]) {
            number++;
            index = i;
        }
    }

    // 总个数减去最大不重叠区间的个数
    return count - number;
}

// LeetCode指定调用方法
public int eraseOverlapIntervals(int[][] intervals) {
		
    // 如果区间为空，则直接返回0
    int count = intervals.length;
    if (count == 0) return 0;

    // 根据区间结尾排序从小到大排序
    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[1] - o2[1];
        }
    });

    // 动态规划
    int[] dp = new int[count];
    int number = 1;
    dp[0] = 1;
    // 求出dp
    for (int i = 1; i < count; i++) {
        // 遍历第个i区间前的dp，判断是否能与第i个区间不重叠，通过遍历得出能与第i个区间不重叠的拥有最大不重叠区间个数的dp，将其加上第i个区间，则为dp[i]
        for (int j = i - 1; j >= 0; j--) {
            // 判断第i个区间是否与第j个区间重叠
            if (intervals[i][0] >= intervals[j][1])  {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        // 记录当前的最大不重叠区间的个数
        number = Math.max(number, dp[i]);
    }

    // 总个数减去最大不重叠区间的个数
    return count - number;
}