Non-overlapping Intervals

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:

1. You may assume the interval's end point is always bigger than its start point.
2. 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.

For non-overlapping intervals, the start time should be larger than or equal to previous end time. Thus we sort the interval based on end time, then we initialize an end time to Integer.MIN_VALUE. After that, compare each interval's start time with the end time. If the start time is not smaller than "end time", we update the end time, this will be the latest time for all non-overlapping intervals. If the start time is smaller than the end time, we increment result, this is the interval we need to remove. The overall complexity should be O(nlogn) for sorting.

public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        
        Arrays.sort(intervals, new Comparator () { 
            @Override
            public int compare(Interval i1, Interval i2) {
                if (i1.end != i2.end) {
                    return i1.end - i2.end;
                } else {
                    return i1.start - i2.start;
                }
            }
        });
        
        int rst = 0,  end = Integer.MIN_VALUE;
        for (Interval interval : intervals) {
            if (end <= interval.start) {
                end = interval.end;
            } else {
                rst++;
            }
        }
        return rst;
    }