435. Non-overlapping Intervals

题目描述和难度

  • 题目描述:

给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

注意:

  1. 可以认为区间的终点总是大于它的起点。
  2. 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后,剩下的区间没有重叠。

示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

思路分析

求解关键:首先将问题转化为这些子区间最多可以构成多少个不重合的子区间。

思路1:使用动态规划,用类似最长上升子序列一样的思路来求解。

思路2:使用贪心算法。

参考解答

参考解答1

import java.util.Arrays;
import java.util.Comparator;

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}

/**
 * 动态规划的写法:
 * 先将原问题转换成,最多可以构成多少互不重叠的子区间
 * 然后为最长上升子序列问题使用动态规划求解
 * 最后将子区间的数量 - 上一步所得的结果
 */
public class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        int ilen = intervals.length;
        if (ilen == 0) {
            return 0;
        }

        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.start != o2.start) {
                    return o1.start - o2.start;
                }
                return o1.end - o2.end;
            }
        });

        // dp[i] 表示以 intervals[i] 为结尾的区间能够成的最长不重叠的区间序列有几个
        int[] dp = new int[ilen];
        Arrays.fill(dp, 1);
        for (int i = 1; i < ilen; i++) {
            for (int j = 0; j < i; j++) {
                if (intervals[i].start >= intervals[j].end) {
                    dp[i] = Integer.max(dp[i], dp[j] + 1);
                }
            }
        }
        // System.out.println(Arrays.toString(dp));
        int res = dp[0];
        for (int i = 1; i < ilen; i++) {
            res = Integer.max(res, dp[i]);
        }
        return ilen - res;
    }
}

参考解答

参考解答2

import java.util.Arrays;
import java.util.Comparator;

/**
 * 贪心算法:如果区间结尾得越早,后面能够接上一个新区间的概率就越大
 */
public class Solution2 {

    public int eraseOverlapIntervals(Interval[] intervals) {
        int ilen = intervals.length;
        if (ilen == 0) {
            return 0;
        }
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.end != o2.end) {
                    return o1.end - o2.end;
                }
                return o1.start - o2.start;
            }
        });
        int res = 1;
        int pre = 0;
        for (int i = 1; i < ilen; i++) {
            if (intervals[i].start >= intervals[pre].end) {
                res++;
                pre = i;
            }
        }
        return ilen - res;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0435-non-overlapping-intervals ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com