JAVA Solution beats 99.26% - solve by finding max non-overlapping intervals

• The basic idea is finding the maximum non-overlapping intervals, and the erased intervals count is the whole length minus the non-overlapping intervals count.
For example:
[1,2],[2,3],[1,3],[3,4]
after sorting:
[1,2],[1,3],[2,3],[3,4]
the max non-overlapping intervals are:
[1,2],[2,3],[3,4] => count = 3;
the intervals that should be removed is [1,3], and the count = len - max_non_overlapping = 4 - 3 = 1

``````public int eraseOverlapIntervals(Interval[] intervals) {
Arrays.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
if (a.start == b.start) return a.end - b.end;
return a.start - b.start;
}
});

int len = intervals.length;
if (len == 0) {
return 0;
}
int maxNonOverLapping = 1, prevStart = intervals[0].start, prevEnd = intervals[0].end;
for (int i = 1; i < len; i++) {
if (prevEnd > intervals[i].start && intervals[i].end < prevEnd) {
// if the current interval has smaller end value, replace previous interval with current on to allow more future non-overlapping intervals
prevEnd = intervals[i].end;
} else if (prevEnd <= intervals[i].start) {
// The current interval is non-overlapping interval to previous interval
maxNonOverLapping++;
prevStart = prevEnd;
prevEnd = intervals[i].end;
}
}
return len-maxNonOverLapping;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.