[代码随想录]Day31-贪心算法part05
题目：435. 无重叠区间
思路：
移除最少就是保留最多，和昨天最后一个题一样就是选出最多的不重叠区间。
记住一点——右边界越小，后续可以选取的范围就越大，可能选取到的就越多
代码：
func eraseOverlapIntervals(intervals [][]int) int {
sort.Slice(intervals,func(i,j int) bool {
return intervals[i][1] < intervals[j][1]
})
res := 0
index := math.MinInt
for _, x := range intervals {
if x[0] >= index {
index = x[1]
continue
}
res++
}
return res
}
参考：
代码随想录
题目：763. 划分字母区间
思路：
这道题在于覆盖的区间会互相影响，因此不断地更新右区间，直到i走到了right右边界就说明后续的区间不与这一次的区间有交集。
代码：
func partitionLabels(s string) []int {
res := []int{}
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 {
sort.Slice(intervals,func(i,j int)bool {
return intervals[i][0] < intervals[j][0]
})
res := [][]int{}
lens := len(intervals)
left, right := intervals[0][0], intervals[0][1]
for i := 1; i < lens; i++ {
if intervals[i][0] > right {
res = append(res, []int{left,right})
left = intervals[i][0]
right = intervals[i][1]
continue
}
if intervals[i][1] > right {
right = intervals[i][1]
}
}
res = append(res, []int{left,right})
return res
}
参考：
代码随想录