###### tags: `Leetcode` `medium` `greedy` `sort` `array` `python` `c++`

# 435. Non-overlapping Intervals

## [題目連結:] https://leetcode.com/problems/non-overlapping-intervals/description/

## 題目:
Given an array of intervals ```intervals``` where ```intervals[i] = [starti, endi]```, 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.

## 解題想法:
* 此題為給一堆區間，求需要移除多少區間可使得剩下的區間皆沒重疊
* Greedy:
* **需先排序好**
* head=intervals[0][1]
* 作為比較的對象
* 取區間**右邊**的值
* for遍歷所有區間
* 分別查看當前區間**左邊**的值
* Case1: 若小於head
* 表示遇到重疊了
* 則需更新head，min(head,intervals[i][1])
* 且res+=1，表示目前的head與interval[i]兩者有一個可以被刪掉
* Case2: 大於等於head
* 表示沒重疊
* 移動head繼續往後遍歷

## Python:

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        if len(intervals)==0:
            return 0
        intervals.sort()
        head=intervals[0][1] #取[1,2]中的'2'
        res=0 #可刪掉的數量
        for i in range(1,len(intervals)):
            #往後找 看其左邊的值: 若小於head 則代表重疊了
            if intervals[i][0]<head:
                head=min(head,intervals[i][1]) #選右邊最小的當head
                res+=1 #目前的head與interval[i]兩者有一個可以被刪掉
            else: #沒重疊 移動head繼續找
                head=intervals[i][1]
        return res

result=Solution()
intervals = [[1,2],[2,3],[3,4],[1,3]]
ans=result.eraseOverlapIntervals(intervals)
print(ans)

## C++:

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int head=intervals[0][1], res=0;
        for (int i=1; i<intervals.size(); i++){
            if (intervals[i][0]<head){
                res+=1;
                head=min(head, intervals[i][1]);
            }
            else
                head=intervals[i][1];
        }
        return res;
    }
};