【代码随想录】算法训练计划36

贪心

1、435. 无重叠区间

题目：
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

思路：

• 贪心，重叠个数，和射气球一样,重叠区间

func eraseOverlapIntervals(intervals [][]int) int {// 代码一刷sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]})res := 0for i:=1; i<len(intervals); i++ {if intervals[i][0] < intervals[i-1][1] {res++intervals[i][1] = min(intervals[i][1], intervals[i-1][1])}}return res
}
func min(a,b int) int {if a>b {return b};return a}

2、763. 划分字母区间

题目：
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]

思路：

• ，很有意思，贪心，就是，记录最大值

func partitionLabels(s string) []int {// 代码一size, left, right := len(s), 0, 0res := []int{}map1 := make(map[byte]int, 26)for i:=0; i<size; i++ {map1[s[i]] = i}for i:=0; i<size; i++ {right = max(right, map1[s[i]])if i==right {res = append(res, right-left+1)left = i+1}}return res
}
func max(a,b int)int{if a>b {return a}; return b}

3、56. 合并区间

题目：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

思路：

• 简单，贪心,区间问题

func merge(intervals [][]int) [][]int {// 代码一刷sort.Slice(intervals, func(i, j int) bool {return intervals[i][0]<intervals[j][0]})res := make([][]int, 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, right = intervals[i][0], intervals[i][1]} else {right = max(right, intervals[i][1])}}res = append(res, []int{left, right})return res
}
func max(a, b int)int{if a>b {return a}; return b}