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 。