leetcode-435-Non-overlapping-Intervals

非重复区间的一个题目，思路比较清晰,感觉和406题有点异曲同工之妙。

题目描述

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example

Example 1:

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [[1,2],[1,2],[1,2]]
Output: 2

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

Example 3:

Input: [[1,2],[2,3]]
Output: 0

Explanation: You don’t need to remove any of the intervals since they’re already non-overlapping.

解题思路

贪心算法

巧妙之处

要记得按照从小到大的顺序进行排序,然后看后一个区间的头是否在前一个区间内，如果没有，那么不用删，如果在，那么肯定要删一个。要么删除前面那个区间，要么删除后面那个区间。比如说[1,3]和[2,4],那么因为2在[1,3]内，所以这个时候肯定要删除[2,4],因为[2,4]在[1,3]更加靠后的位置。但是如果前面是[1,10],然后后面有[2,3]和[4,5]这种情况最好是删除第一个[1,10]，因为[1,10]包含的区间更加靠后。

解题代码

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end());
       
        int res = 0;
        vector<int> temp;
        for(auto p : intervals){
            if( temp.empty() || p[0] >= temp[1]){
                temp = p; 
            }else{
                res++;
                temp = p[1] < temp[1]? p:temp;
            }
        }
        return res;
    }
};

以上，本题结束！