# 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_i, end_i]</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⁵</code>
- <code>intervals[i].length == 2</code>
- <code>-5 * 10⁴ <= start_i < end_i <= 5 * 10⁴</code>

## Solution 1 - Greedy
#### 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++

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.