Implement the eraseOverlapIntervalsCount method that returns how many intervals must be removed to avoid overlaps.
The input contains a list of intervals, where each interval is represented as [start, end].
Your task is to return the minimum number of intervals that must be removed so that the remaining intervals do not overlap.
For example, in [[1,2],[2,3],[3,4],[1,3]], removing [1,3] leaves non-overlapping intervals, so the answer is 1.
Example 1
[[1,2],[2,3],[3,4],[1,3]]41Example 2
[[1,2],[1,2],[1,2]]32Example 3
[[1,2],[2,3]]20Keep as many non-overlapping intervals as possible, then the removed count will be minimum.
Sort intervals by ending time. Choose the interval that ends earliest because it leaves the most space for future intervals. For every next interval, if its start is before the last selected end, it overlaps and should be counted as removed. Otherwise, keep it and update the last selected end.
This greedy choice minimizes removals.
Pseudocode:
function eraseOverlapIntervalsCount(intervals, size):
if size == 0:
return 0
sort intervals by end value ascending
removed = 0
lastEnd = intervals[0][1]
for i from 1 to size - 1:
if intervals[i][0] < lastEnd:
removed++
else:
lastEnd = intervals[i][1]
return removed