输入:

相信很多同学看到这道题目都冥冥之中感觉要排序但是究竟是按照右边界排序还是按照左边界排序呢

我来按照右边界排序从左向右记录非交叉区间的个数。

最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

当确定区间

接下来就是找大于区间1结束位置的区间是从区间4开始。

那有同学问了为什么不从区间5开始别忘了已经是按照右边界排序的了。

区间4结束之后再找到区间6所以一共记录非交叉区间的个数是三个。

总共区间个数为6减去非交叉区间的个数3。

移除区间的最小数量就是3。

C代码如下

eraseOverlapIntervals(vectorvectorint

intervals)

有一个快排空间复杂度O(n)有一个快排最差情况(倒序)时需要n次递归调用。

因此确实需要O(n)的栈空间

补充1

eraseOverlapIntervals(vectorvectorint

intervals)

intervals[i][1]);count;}}return

count;}

eraseOverlapIntervals(vectorvectorint

intervals)

intervals[i][1]);count;}}return

count;}

window)非常像弓箭的数量就相当于是非交叉区间的数量只要把弓箭那道题目代码里射爆气球的判断条件加个等号认为[01][12]不是相邻区间然后用总区间数减去弓箭数量

(opens

eraseOverlapIntervals(vectorvectorint

intervals)

eraseOverlapIntervals(vectorvectorint

intervals)

。

我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。

注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是

输入s

题目要求同一字母最多出现在一个片段中那么如何把同一个字母的都圈在同一个区间里呢

在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。

此时前面出现过所有字母最远也就到这个边界了。

统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点

明白原理之后代码并不复杂如下

};时间复杂度O(n)空间复杂度O(1)使用的hash数组是固定大小

这道题目leetcode标记为贪心算法说实话我没有感受到贪心找不出局部最优推出全局最优的过程。

就是用最远出现距离模拟了圈字符的行为。

但这道题目的思路是很巧妙的所以有必要介绍给大家做一做感受一下。

(opens

统计字符串中所有字符的起始和结束位置记录这些区间(实际上也就是435.无重叠区间

(opens

window)题目里的输入)将区间按左边界从小到大排序找到边界将区间划分成组互不重叠。

找到的边界就是答案。

class

{hash_filter.push_back(hash[i]);}}return

{vectorint

只不过现在我们要求的是区间分割点vectorvectorint

hash

这几道题都是判断区间重叠区别就是判断区间重叠后的逻辑本题是判断区间重贴后要进行区间合并。

所以一样的套路先排序让所有的相邻区间尽可能的重叠在一起按左边界或者右边界排序都可以处理逻辑稍有不同。

按照左边界从小到大排序之后如果

其实就是用合并区间后左边界和右边界作为一个新的区间加入到result数组里就可以了。

如果没有合并就把原区间加入到result数组。

C代码如下

排序的参数使用了lambda表达式sort(intervals.begin(),

intervals.end(),

第一个区间就可以放进结果集里后面如果重叠在result上直接合并result.push_back(intervals[0]);

for

合并区间只更新右边界就好因为result.back()的左边界一定是最小值因为我们按照左边界排序的result.back()[1]

intervals[i][1]);

{result.push_back(intervals[i]);

区间不重叠