Leetcode-435 non-overlapping intervals

Description

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

You may assume the interval’s end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

分析

首先以第一个元素的为基准对各个区间排序
初始化冲突计数器为 0，设置两个指针，一前一后，每个指针指向一个区间
如果两个指针指向的区间有冲突，则前指针指向最小覆盖的区间，后指针向后移动一个区间，冲突计数器加一
如果两指针指向的区间没有冲突，则两指针平滑向后移动一个区间
返回冲突计数器中的值。

程序设计

储备知识

Java 比较器

区间的排序是依据第一个元素进行比较操作的。Java 有两种方式提供比较功能，其一是实现 Comparable 接口，使类具有比较的功能。第二种是实现 Comperator 接口，比较规则定义在该接口提供的 compare 方法中。

class IntervalComparator implements Comparator<Interval> {
    public int compare(Interval a, Interval b) {
        return a.start - b.start;
    }
}

// 其中 Interval 对象定义如下
class Interval {
    int start, end;
    Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

在 Java 8 中，还可以使用 Lambda 表达式创建比较器，如下

1	Arrays.sort(intervals, (Interval x, Interval y) -> x.start - y.start);

代码如下

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
    	if (null == intervals || intervals.length == 0) {
            return 0;
        }
        int conflict = 0;
        int j = 0;
        
        Arrays.sort(intervals, (int[] x, int[] y) -> x[0] - y[0] );
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[j][1] > intervals[i][0]) {
                conflict++;
                // j point min zone
                j = intervals[j][1] < intervals[i][1] ? j : i;
            } else {
                j = i;
            }
        }
        return conflict;
    }
}

本例使用的是贪心思想，如果有冲突，则指针指向最小覆盖区间，这就是贪心的思想。