Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Example 1:
**Input:** intervals = [[1,2],[2,3],[3,4],[1,3]]
**Output:** 1
**Explanation:** [1,3] can be removed and the rest of the intervals are non-overlapping.
Example 2:
**Input:** intervals = [[1,2],[1,2],[1,2]]
**Output:** 2
**Explanation:** You need to remove two [1,2] to make the rest of the intervals non-overlapping.
Example 3:
**Input:** intervals = [[1,2],[2,3]]
**Output:** 0
**Explanation:** You don't need to remove any of the intervals since they're already non-overlapping.
Constraints:
1 <= intervals.length <= 105
intervals[i].length == 2
-5 * 104 <= starti < endi <= 5 * 104
ac: Greedy
class Solution {
public int eraseOverlapIntervals(Interval[] intervals) {
// edge cases
if (intervals.length <= 1) return 0;
Arrays.sort(intervals, (a, b) -> {return a.start != b.start ? a.start - b.start : a.end - b.end;});
Interval prev = intervals[0];
int count = 0;
for (int i = 1; i < intervals.length; i++) {
Interval curr = intervals[i];
if (curr.start < prev.end) { // overlap
count++; // have to remove one
prev = curr.end > prev.end ? prev : curr;
} else {
prev = curr;
}
}
return count;
}
}
// O(NlogN) time.
// Iterate, if there are 2 intervals overlap, we have to remove one. Which one? The one with larger endpoints, because it has more possibility to overlap with others.