Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note:
- You may assume the interval's end point is always bigger than its start point.
- Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Example 2:
Input: [ [1,2], [1,2], [1,2] ]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:
Input: [ [1,2], [2,3] ]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
思路
思路与merge interval一致
- 通过Comparator对intervals进行排序，先按照区间的start升序，如果start相等再按照end升序排序
- 如果后一个区间与前一个区间重合，那么说明后一区间需要去掉才能保证不重合，此时count+1.
- 如果前后2个区间不重合，那么更新前一区间的起始范围，继续判断。
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public int eraseOverlapIntervals(Interval[] intervals) {
int count = 0;
if (intervals == null || intervals.length == 0) {
return count;
}
Arrays.sort(intervals, (o1, o2) -> o1.start == o2.start? o1.start - o2.start : o1.end - o2.end);
Interval pre = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i].start < pre.end) {
// pre.end = Math.max(pre.end, intervals[i].end);
count++;
continue;
} else {
pre = intervals[i];
}
}
return count;
}
}
Merge Intervals
思路
- （考点）用comparator自定义sort的方式
- 设置第0个元素为last interval，
- 从intervals的第1个元素开始遍历intervals Array，每次为curInterval.
- 比较，curInterval.start >= lastInterval.last ： 更新last interval的范围，此时并不向result中加入该更新的interval，因为后面后可能还有需要merge到当前interval的元素
- 如，cur 与 last无重合：result.add(last); last = curInterval
- ！！！记得把最后一个last加入到结果中
/**
* Definition of Interval:
* public class Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
*/
public class Solution {
/*
* @param intervals: interval list.
* @return: A new interval list.
*/
public List<Interval> merge(List<Interval> intervals) {
// write your code here
// 1. ！！！用comparator自定义sort的方式（考点）
// 2. 设置第0个元素为last interval，
// 3. 从intervals的第1个元素开始遍历intervals Array，每次为curInterval
// 比较，curInterval.start >= lastInterval.last =》 更新last interval的范围，此时并不向result中加入该更新的interval，因为后面后可能还有需要merge到当前interval的元素
// 如，cur 与 last无重合：result.add(last); last = curInterval
// 4. ！！！记得把最后一个last加入到结果中
List<Interval> result = new ArrayList<Interval>();
if (intervals == null || intervals.size() < 1) {
return result;
}
//1. Sort intervals based on start
Collections.sort(intervals, new intervalComparator());
//2. merge
Interval lastInt = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval curInt = intervals.get(i);
if (curInt.start <= lastInt.end) { //last的end可能比cur的end更大，或小
lastInt.end = Math.max(lastInt.end, curInt.end);
} else {
result.add(lastInt);
lastInt = curInt;
}
}
//3. DONT forget the LAST lastInt
result.add(lastInt);
return result;
}
}
//@override Comparator interface
class intervalComparator implements Comparator<Interval> {
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
}
