大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位同学在吐槽360的面试官，说是有史以来体验最差的一次面试，全程面试官语气轻蔑，不停地贬低嘲讽，完全没有一点尊重。
面试官代表了一个公司的形象，还是建议360加强对面试官的筛选和培训。大家在面试的过程中有没有遇到过类似的情况，可以评论区中说说你的经历。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道360的面试原题「无重叠区间」。
题目描述
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
举个例子：
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
思路解析
首先要明确怎样的区间算是不重叠的，[1, 2]和[2, 3]这两个区间虽然都包含2，但是根据题目的意思他俩是不重叠的。
接下来要制订移除重叠区间的策略。假设区间a=[1, 3]，b=[4, 6]，c=[2, 5]，先对三个区间以区间起点为主键进行排序。如下图，相邻的a、c存在重叠。
如果移除区间 a，那么b和c依旧存在重叠，那么还需移除区间b和c中的一个才能保证剩下的区间不重叠。这个时候总共需要移除2次。如果移除区间 c，a和b不存在重叠。这个时候总共需要移除1次。
总结上面的两种情况，我们发现相邻两个重叠区间中，移除区间终点较大的那个区间可以保证最终移除的区间数是最少的。
下面我们给出c++和python两种代码实现。
C++代码
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int intervals_len = intervals.size();
if (intervals_len == 0)
return 0;
//interval的第一个元素作为key排序
sort(intervals.begin(),intervals.end(),[](const vector<int>& interval1,const vector<int>& interval2){
return interval1[0] < interval2[0];
});
int res = 0;
int tmpEnd = intervals[0][1];
for (int i = 1; i < intervals_len; ++i) {
//没有重叠
if (intervals[i][0] >= tmpEnd) {
tmpEnd = intervals[i][1];
//有重叠
} else {
//移除重叠区间[start1，end1]和[start2, end2]中end1、end2值较大的那个区间。
tmpEnd = min(tmpEnd, intervals[i][1]);
++res;
}
}
return res;
}
};
python代码
class Solution(object):
def eraseOverlapIntervals(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: int
"""
intervals_len = len(intervals)
if intervals_len == 0:
return 0
# 根据区间的第一个元素进行排序
intervals.sort(key=lambda x: x[0])
res = 0
tmpEnd = intervals[0][1]
for i in range(1, intervals_len):
# 如果没有重叠
if intervals[i][0] >= tmpEnd:
tmpEnd = intervals[i][1]
# 如果有重叠
else:
# 移除重叠区间中 end 值较大的那个区间
tmpEnd = min(tmpEnd, intervals[i][1])
res += 1
return res
复杂度分析
时间复杂度： 首先排序的时间复杂度是O(nlogn)，遍历一遍数组intervals需要O(n)，总的时间复杂度是O(nlogn)。其中n为intervals的长度。
空间复杂度： 只需要几个整型变量，故时间复杂度为O(1)。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
