在github:https://github.com/young yangyang 04/leet代码- master中总结了有关算法学习的资料。 其中还有leet代码刷题攻略、各类型经典刷题顺序、思维导图。 如果对你有用的话一定会得到

435. 无重叠区间

主题链接： https://leet代码- cn.com/problems/non-overlapping-intervals /

给出某个区间的集合，找出需要删除区间以使剩下的区间不相互重叠的最小数量。

注意一般认为：区间的终点总是大于其起点。 区间[ 1，2 ]和[ 2，3 ]的边界相互“接触”，但相互不重叠。

例1:输入： [ [ 1，2 ]，[ 2，3 ]，[ 3，4 ]，[ 1，3 ] ]输出：说明3360在除去[ 1，3 ]之后，其余的区间不重叠。

示例2:输入： [ [ 1，2 ]，[ 1，2 ] ]输出： 2说明：必须删除两个[ 1，2 ]，以免其余的区间重叠。

示例3:输入： [ [ 1，2 ]，[ 2，3 ] ]输出：说明：不重复，因此不需要删除区间。

思路

“我想很多学生看到这个主题后感觉在冥王星上，是按右边界排序，还是按左边界排序？ “”

这其实是个难点！

按右边距排序将导致从左到右遍历。 右边距越小越好，所以右边距越小，下一个区间剩下的空间越大。 因此，从左向右遍历，右边距小的优先。

如果按左边距排序，将从右向左遍历。 左边距的数值越大越好(靠右)，所以前面区间的空间越大，可以从右向左遍历。

如果按左边距排序，然后再从左向右遍历，则必须处理各区间右边距的各种情况。

有些同学可能会做这个题目模拟真的重复区间的行为，但是这很麻烦，所以把区间删掉。

主题只是要求删除区间的数量，没有必要去实际的伪删除区间！

“按右边距排序，从左到右记录非交叉区间的数量。 最后从区间总数中减去非交叉区间的个数就是应该删除的区间的个数”。

此时问题是要求非交叉区间的最大个数。

重新排列右边距后，局部最优：优先选择右边距小的区间，所以从左到右扫描，增大下一个区间留下的空间，尽量避免交叉。 全局最优：选择最多的非交叉区间。

局部最优打出全局最优，试着贪婪吧！

这里记录非交叉区间的个数还是有诀窍的。 图：

435 .没有重复区间

区间、1、2、3、4、5、6都沿着右边界按顺序排列。

因为每次取非交叉区间时都会建立分割点，使右边距最小，所以第一条分割线位于区间1的结束位置。

然后寻找比区间1的结束位置大的区间。 从区间4开始。 “那为什么不从区间5开始呢？ 有个同学听说了。 别忘了已经在右边界排序了”。

区间4结束后，因为发现了区间6，所以非交叉区间的数量记录了3个。

总区间的个数为6，减去非交叉区间的个数3。 删除区间的最小数量为3。

c代码如下所示。

类解决方案{2}

公共：

//按区间的右边距排序

staticboolcmp (概念中心，概念中心)

t;int>& b) {         return a[1] < b[1];     }     int eraseOverlapIntervals(vector<vector<int>>& intervals) {         if (intervals.size() == 0) return 0;         sort(intervals.begin(), intervals.end(), cmp);         int count = 1; // 记录非交叉区间的个数         int end = intervals[0][1]; // 记录区间分割点         for (int i = 1; i < intervals.size(); i++) {             if (end <= intervals[i][0]) {                 end = intervals[i][1];                 count++;             }         }         return intervals.size() - count;     } }; 时间复杂度：O(nlogn) ，有一个快排空间复杂度：O(1)

大家此时会发现如此复杂的一个问题，代码实现却这么简单！

总结

本题我认为难度级别可以算是hard级别的！

总结如下难点：

难点一：一看题就有感觉需要排序，但究竟怎么排序，按左边界排还是右边界排。难点二：排完序之后如何遍历，如果没有分析好遍历顺序，那么排序就没有意义了。难点三：直接求重复的区间是复杂的，转而求最大非重复区间个数。难点四：求最大非重复区间个数时，需要一个分割点来做标记。

「这四个难点都不好想，但任何一个没想到位，这道题就解不了」。

一些录友可能看网上的题解代码很简单，照葫芦画瓢稀里糊涂的就过了，但是其题解可能并没有把问题难点讲清楚，然后自己再没有钻研的话，那么一道贪心经典区间问题就这么浪费掉了。

贪心就是这样，代码有时候很简单（不是指代码短，而是逻辑简单），但想法是真的难！

这和动态规划还不一样，动规的代码有个递推公式，可能就看不懂了，而贪心往往是直白的代码，但想法读不懂，哈哈。

「所以Carl把本题的难点也一一列出，帮大家不仅代码看的懂，想法也理解的透彻！」

循序渐进学算法，认准「代码随想录」就够了，值得介绍给身边的朋友同学们！

我是程序员Carl，个人主页：https://github.com/youngyangyang04

这里每天8:35准时推送一道经典算法题目，我选择的每道题目都不是孤立的，而是由浅入深，环环相扣，帮你梳理算法知识脉络，轻松学算法！

@代码随想录 期待你的关注