> For the complete documentation index, see [llms.txt](https://tonyding.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tonyding.gitbook.io/algorithm/lc-435-non-overlapping-intervals.md).

# LC 435 Non-overlapping Intervals(M)

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.

`public int eraseOverlapIntervals(Interval[] intervals)`

**边界条件** 如果 intervals 为空，返回0

## 解题思路

以interval 的 end 进行排序比较， 在排序后的数组中，记录不重叠的 interval, 用总数减去这个值，就是需要去除的个数

```java
public int eraseOverlapIntervals(Interval[] intervals) {
    if (intervals.length == 0)
        return 0;
    Comparator<Interval> interComp = new Comparator<Interval>(){
        public int compare(Interval i1, Interval i2){
            return i1.end - i2.end;
        }
    };
    Arrays.sort(intervals, interComp);

    int end = intervals[0].end;
    int count = 1;
    for(int i = 1; i < intervals.length; i++){
        if(intervals[i].start>=end){
            end = intervals[i].end;
            // non-overlaping count
            count ++;
        }
    }
    // remove interval count
    return intervals.length - count;
}
```