# Non-overlapping Intervals

Leave a commentDecember 18, 2016 by oneOokay

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:1Explanation:[1,3] can be removed and the rest of intervals are non-overlapping.

**Example 2:**

Input:[ [1,2], [1,2], [1,2] ]Output:2Explanation:You need to remove two [1,2] to make the rest of intervals non-overlapping.

**Example 3:**

Input:[ [1,2], [2,3] ]Output:0Explanation:You don't need to remove any of the intervals since they're already non-overlapping.

这题乍看上去跟之前的intervals和overlapping的都差不多，但是其实不太一样。

这题求最少需要移除的interval数目，其实就是等同于求集合中存在最多的non-overlapping interval的数目。

其实也就是求我们有这么些个任务，可能存在overlapping，求最多能够完成多少个任务这样类似的题目。

这个是一个Classic Greedy problem，如果像之前的题目一样把intervals按照start time排列，并不能达到目的。因为如果最早开始的task恰好持续的时间最长，那么并不能得到最优解。所以应该按照task的结束顺序进行排列。

```
public int eraseOverlapIntervals(Interval[] intervals) {
if (intervals == null || intervals.length <= 1){
return 0;
}
Arrays.sort(intervals, new Comparator<Interval>(){
public int compare(Interval i1, Interval i2){
return i1.end - i2.end;
}
});
int end = intervals[0].end;
int count = 1; //注意初始的count=1，因为至少为1
for(int i = 1; i < intervals.length; i++){
Interval cur = intervals[i];
if (cur.start >= end){
count ++;
end = cur.end;
}
}
return intervals.length - count;
}
```

Advertisements