贪心算法——区间问题

vlambda
2020-08-22

贪心算法——区间问题

贪心——区间问题主要分为两大模型：区间覆盖问题和区间不相交问题。

按照我的习惯先把算法模板贴出来(go语言代码)

sort.Slice(arr,func (i,j int)bool{  return ......  })for i:=0;i<len(arr);i++{  for (){//其他语言的while循环  }}

模板解析

贪心算法——区间问题

对于区间覆盖问题：

给定若干类似区间[3,9][4,6] [2,3] [0,2][2,4]...... 选择尽量少的区间覆盖一个指定的区间[0,t]
看到最多最少一共基本可以锁定为动态规划或者贪心算法
首先应该思考的问题是我们应该怎么选择，看到前边的模板，大家应该知道应该排序，但是怎么排序又成为继续要思考的问题了
为了使每次我们都选择一个区间跨度大，而且能够完全覆盖区间[0,t]，我们应该以每个区间的左端点排序。

区间不相交问题：

给定若干类似区间[1,2], [2,3], [3,4], [1,3] ...... 选择尽量多的区间，使得这些区间两两没有公共点
这道题类似参加聚会问题，最多参加多少场聚会，不能同时参加多场聚会
对于这个模型，上一个排序模型就不适用了，就需要我们去重新思考了
为了使参加的聚会次数最多，每次应该选择时间最早结束，时间跨度最短的聚会，所以每次应该选择以区间的右端点排序且时间区间最短的。

列题解析

贪心算法——区间问题

来看一道腾讯2020校园招聘题，抛去背景是一道区间覆盖问题，直接套用模板（ac）

package mainimport "fmt"import "sort"func main(){ n,l:=0,0 fmt.Scanf("%d %d",&n,&l)
 arr:=make([][]int,n) for i:=0;i<n;i++{ arr[i]=make([]int,2) fmt.Scanf("%d %d",&arr[i][0],&arr[i][1]) } fmt.Println(anser(arr,l))
}func anser(arr [][]int,L int)int{ if len(arr)<=0 || len(arr[0])==0{ return 0 } sort.Slice(arr,func (i,j int)bool{ if arr[i][0]==arr[j][0]{ return arr[i][1]>arr[j][1] } return arr[i][0]<arr[j][0] }) if arr[0][0]!=0{ return -1 }
 count:=0 temp:=0 for i:=0;i<len(arr);i++{ if arr[i][0]>temp{ return -1 }
 end:=arr[i][1] for i+1<len(arr) && arr[i+1][0]<=temp{ i++ end=max(end,arr[i][1]) } count++ temp=end if temp>=L{ return count }
 } return -1
}func max(x,y int)int{ if x>y{ return x } return y}

这两道属于同一个类似（区间不相交问题）（代码一样）

func findMinArrowShots(points [][]int) int {
 sort.Slice(points,func (i,j int)bool{  return points[i][1]<points[j][1] })  count:=0 for i:=0;i<len(points);i++{ x:=points[i][1] for i+1<len(points) && points[i+1][0]<=x{ i++ } count++ 
 } return count

}

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