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

两点：

1.sort intervals by their ends. Why not starts? Draw a picture with some overlapping intervals and see.

a |________|

b |_________|

c |_________|

If interval a overlap with b, dump b, and check a and c. Because if c overlap with a, it will overlap with b for sure (if c.start < a.end, then c.start ** a.end). However if sort by start, when a and b overlap, need to check both pair (a, c) and (b, c), since the following case is possible:
a |___________|
b |__|
c |______|**

2.finding minimum number of intervals to be removed, equals to finding max number of non-overlapping intervals

public int eraseOverlapIntervals(Interval[] intervals) { if (intervals == null || intervals.length < 2) return 0; Arrays.sort(intervals, new Comparator<Interval>(){ public int compare(Interval i1, Interval i2) { return i1.end - i2.end; } }); int count = 1; // max number of non-overlapping intervals int end = intervals[0].end; for (int i = 1; i < intervals.length; i++) { if (intervals[i].start >= end) { end = intervals[i].end; count++; } } return intervals.length - count; }