435. 无重叠区间(思维)

Ch_Zaqdt

发布于 2020-02-17 11:12:45

9480

文章被收录于专栏：Zaqdt_ACMZaqdt_ACM

题目链接：https://leetcode-cn.com/problems/non-overlapping-intervals/submissions/

刚做完一道区间的题，又随机刷出来一道区间的题，那么和上一道(上一篇博客)那道题大同小异，我们考虑一下如果两个区间有重叠，那么一定是要删除一个的，那么删除哪一个就需要进行比较了，首先我们按照区间的左端点进行排序。遍历区间，如果相邻的两个区间重叠了，那么最优的删除就是看谁的右端点最靠右，不难想到越是靠右就越有可能覆盖到后面的区间，所以按照这个思路删除就好了。

AC代码：

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int ans = 0;
        int len = intervals.size();
        if(len == 0) return 0;
        sort(intervals.begin(), intervals.end(),[](vector<int>& a,vector<int>& b){
            return a[0] < b[0];
        });
        int x = intervals[0][0], y = intervals[0][1];
        for(int i=1;i<len;i++){
            if(y > intervals[i][0]){
                if(y > intervals[i][1]){
                    x = intervals[i][0];
                    y = intervals[i][1];
                    ans ++;
                }
                else{
                    ans ++;
                }
            }
            else{
                x = intervals[i][0];
                y = intervals[i][1];
            }
        }
        return ans;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/02/04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历