05 August 2008
给定一个区间区间数组，其中区间 [i] = [starti, endi]，返回需要删除的最小区间数，以使其余区间不重叠。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); // sort the list based on the starting index
int result = 0;
LinkedList<int[]> merged = new LinkedList(); //linkedlist which will don't contain the overlapping intervals
for (int[] interval : intervals) {
if (merged.isEmpty() || merged.getLast()[1] <= interval[0]) { //add the interval to the list if the ending index of last interval is smaller than the starting index of current i.e they are not overlapping
merged.add(interval);
} else {
//the last interval is overlapping with current one
result++;
if (merged.getLast()[1] > interval[1]) { //if the last interval's end idx is greater than the start idx of the current interval then remove the last interval and add the current interval to the list
merged.removeLast();
merged.add(interval);
}
}
}
return result;
}
}