LC 435 Non-overlapping Intervals(M)

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.

public int eraseOverlapIntervals(Interval[] intervals)

边界条件 如果 intervals 为空，返回0

解题思路

以interval 的 end 进行排序比较， 在排序后的数组中，记录不重叠的 interval, 用总数减去这个值，就是需要去除的个数

public int eraseOverlapIntervals(Interval[] intervals) {
    if (intervals.length == 0)
        return 0;
    Comparator<Interval> interComp = new Comparator<Interval>(){
        public int compare(Interval i1, Interval i2){
            return i1.end - i2.end;
        }
    };
    Arrays.sort(intervals, interComp);

    int end = intervals[0].end;
    int count = 1;
    for(int i = 1; i < intervals.length; i++){
        if(intervals[i].start>=end){
            end = intervals[i].end;
            // non-overlaping count
            count ++;
        }
    }
    // remove interval count
    return intervals.length - count;
}