---
# System prepended metadata

title: 0435. Non-overlapping Intervals
tags: [Leetcode, Merge Interval, Medium, Greedy]

---

# 0435. Non-overlapping Intervals
###### tags: `Leetcode` `Medium` `Merge Interval` `Greedy`
Link: https://leetcode.com/problems/non-overlapping-intervals/
## 思路 $O(NlogN)$ $O(N)$
Find the maximum number of intervals that are not overlapping.
贪心算法
假设interval $a$和$b$ overlap, 一定是选end小的那个，因为如果选end大的那个也能achieve maximum number of intervals，那么选end小的一样可以
## Code
```java=
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b)->(a[1]-b[1]));
        int cnt = 1;
        int prev = intervals[0][1];
        for(int i = 1;i < intervals.length;i++){
            if(intervals[i][0]>=prev){
                cnt++;
                prev = intervals[i][1];
            }
        }
        return intervals.length-cnt;
    }
}
```