435.无重叠区间

题目描述

题解

贪心算法

正确的思路其实很简单，可以分为以下三步：

1. 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
2. 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
3. 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。

把这个思路实现成算法的话，可以按每个区间的 end 数值升序排序，因为这样处理之后实现步骤 1 和步骤 2 都方便很多:

现在来实现算法，对于步骤 1，由于我们预先按照 end 排了序，所以选择 x 是很容易的。

由于我们事先排了序，不难发现所有与 x 相交的区间必然会与 x 的 end 相交；如果一个区间不想与 x 的 end 相交，它的 start 必须要大于（或等于）x 的 end：

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0)
        return 0;
    Arrays.sort(intervals, (int[] a, int[] b) -> {
        return a[1] - b[1];
    });

    int count = 1;
    int x_end = intervals[0][1];
    for (int[] interval : intervals) {
        int start = interval[0];
        if (start >= x_end) {
            count++;
            x_end = interval[1];
        }
    }
    return intervals.length - count;

}