Non-overlapping Intervals

https://leetcode.com/problems/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.

Thoughts

https://en.wikipedia.org/wiki/Interval_scheduling#Interval_Scheduling_Maximization

Code

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        int res = 0;
        Arrays.sort(intervals, (a, b) -> a.end - b.end);
        Interval last = null;
        for (Interval interval : intervals) {
            if (last == null || last.end <= interval.start) {
                res++;
                last = interval;
            }
        }
        return intervals.length - res;
    }
}

Analysis

时间复杂度O(nlgn)