# 0435. Non-overlapping Intervals
###### tags: `Leetcode` `Medium` `Greedy` `Intervals`
Link: https://leetcode.com/problems/non-overlapping-intervals/description/
## 思路
1. 如果求的是maximum number of non-overlapping intervals，用sort by ending point的方法
2. 如果求的是minimum number of intervals to cover the whole range，用sort by starting point的方法

所以这里我们**sort by ending point**
我们把右边界最小（成为right）的那个区间做为首区间，从排序后的interval中找到所有start小于当前这个右边界right的区间．这些区间都是可以删掉的！这是因为这些区间都互相重合，必然只能保留一个．而保留哪一个呢？就是保留当前这个右边界最小的区间，因为其他区间的右边界都较大，可能会造成对后面区间的重合，有潜在的风险，去掉他们最保险．
## Code

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key=lambda i:i[1])
        count = 0
        end = intervals[0][1]
        n = len(intervals)
        for i in range(1, n):
            if intervals[i][0]<end:
                count += 1
            else:
                end = intervals[i][1]
        return count

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b)->(a[1]-b[1]));
        int idx = 1;
        int count = 0;
        int end = intervals[0][1];
        int n = intervals.length;
        while(idx < n){
            while(idx < n && end>intervals[idx][0]){
                idx++;
                count++;
            }
            if(idx!=n) end = intervals[idx][1];
            idx++;
        }
        return count;
    }
}