---
# System prepended metadata

title: LC 435. Non-overlapping Intervals
tags: [medium, leedcode, Greedy, python, c++]

---

# LC 435. Non-overlapping Intervals

### [Problem link](https://leetcode.com/problems/non-overlapping-intervals/)

###### tags: `leedcode` `python` `c++` `medium` `Greedy`

Given an array of intervals <code>intervals</code> where <code>intervals[i] = [start<sub>i</sub>, end<sub>i</sub>]</code>, return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

**Example 1:** 

```
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
```

**Example 2:** 

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

**Example 3:** 

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

 **Constraints:** 

- <code>1 <= intervals.length <= 10<sup>5</sup></code>
- <code>intervals[i].length == 2</code>
- <code>-5 * 10<sup>4</sup> <= start<sub>i</sub> < end<sub>i</sub> <= 5 * 10<sup>4</sup></code>


## Solution 1 - Greedy
#### Python
```python=
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x: x[1])
        right_edge = intervals[0][1]
        non_overlap = 1

        for left, right in intervals:
            if left >= right_edge:
                non_overlap += 1
                right_edge = right

        return len(intervals) - non_overlap
```
#### C++
```cpp=
class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a[1] < b[1];
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);

        int res = 0;
        int right = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < right) {
                res++;
            } else {
                right = intervals[i][1];
            }
        }
        return res;
    }
};
```

>### Complexity
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(nlogn)        | O(n)             |

## Note
sol1:
python:
無腦選end最小的, 因為選擇end最小的話才不會干預到其他interval.

c++:
無腦選right最小的, 因為選擇right最小的話才不會干預到其他interval.
