435. 无重叠区间(思维)

• 2020 年 2 月 17 日
• 筆記

题目链接：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;      }  };