贪心算法part5 | ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间

---

435. 无重叠区间

思路

重叠问题都需要先排好序，再贪心

思路代码

func eraseOverlapIntervals(intervals [][]int) int {sort.Slice(intervals,func(i,j int)bool{return intervals[i][1]<intervals[j][1]})count:=1end:=intervals[0][1]for i:=1;i<len(intervals);i++{if end<=intervals[i][0]{end=intervals[i][1]count++}}return len(intervals)-count
}

困难

搞清楚左右区间，重叠的条件。
要找出最少删除的数量，也就是找出重叠空间的数量，然后用长度减去即可。

---

763.划分字母区间

思路

这里提供一种与452.用最少数量的箭引爆气球 (opens new window)、435.无重叠区间 (opens new window)相同的思路。

统计字符串中所有字符的起始和结束位置，记录这些区间(实际上也就是435.无重叠区间 (opens new window)题目里的输入)，将区间按左边界从小到大排序，找到边界将区间划分成组，互不重叠。找到的边界就是答案。

官方题解

一想到分割字符串就想到了回溯，但本题其实不用回溯去暴力搜索。

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

如果没有接触过这种题目的话，还挺有难度的。

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

可以分为如下两步：

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

代码

func partitionLabels(s string) []int {var res []int;var marks [26]int;size, left, right := len(s), 0, 0;for i := 0; i < size; i++ {marks[s[i] - 'a'] = i;}for i := 0; i < size; i++ {right = max(right, marks[s[i] - 'a']);if i == right {res = append(res, right - left + 1);left = i + 1;}}return res;
}func max(a, b int) int {if a < b {a = b;}return a;
}

困难

将字符串转换为每个字符的起始位置，终止位置

---

56. 合并区间

思路

与前面类似但又不同

思路代码

func merge(intervals [][]int) [][]int {res:=[][]int{}sort.Slice(intervals,func (i,j int)bool{return intervals[i][0]<intervals[j][0]})left,right:=intervals[0][0],intervals[0][1]for i:=1;i<len(intervals);i++{if right<intervals[i][0]{res=append(res,[]int{left,right})left=intervals[i][0]right=intervals[i][1]}else{right=max(right,intervals[i][1])}}res=append(res,[]int{left,right})return res}func max(i,j int)int{if i>j{return i}return j
}

---

今日收获

重叠问题大致分两类
一类是重叠区间问题（箭射气球）
一类是合并区间问题
做法类似但是处理的逻辑不太相同，左右区间排序的选择也有不同。