题目一
代码与解析
给定二维空间, 一个二维数组
[[10,16],[2,8],[1,6],[7,12]]里每一个数组,代表的是横坐标起点,终点
类似这样,求最少的射箭数
思路:
- 先排序,让这些区间按顺序站好
-
遍历,看当前区间右边界和下一个区间左边界大小关系,大于则res++
-
否则,就要更新最小右边界!!!!!!
详见可以看carl大佬的思路
有一点需要注意: res初始为1这里的关键是 判断左右边界大小和
更新边界points[i][1] = min(points[i-1][1], points[i][1])
func findMinArrowShots(points [][]int) int {
// 请注意
res := 1
// 排序
sort.Slice(points, func(i, j int)bool{
return points[i][0]<points[j][0]
})
for i:=1;i<len(points);i++{
// 看当前区间右边界和下一个区间左边界大小关系,大于则res++
if points[i-1][1]<points[i][0]{
res++
}else{
// 更新最小右边界
points[i][1] = min(points[i-1][1], points[i][1])
}
}
return res
}
func min(i, j int)int{
if i>j{
return j
}else{
return i
}
}
题目二
代码与解析
这道题和上一道题有异曲同工之妙,
这个也是判断左右区间
甚至比上一道简单,只需要找到相应区间,
上一道是找到不重合的左右边界res++
这一道是找到重合的左右边界res++
func eraseOverlapIntervals(intervals [][]int) int {
res:= 0
sort.Slice(intervals, func(i, j int)bool{
return intervals[i][0]<=intervals[j][0]
})
info0, info1 := []int{}, []int{}
for i:=1;i<len(intervals);i++{
info0 = intervals[i-1]
info1 = intervals[i]
// 判断当前区间右边界,和下一区间左边界大小。
// 如果重复,更新最小右边界,res++
if info0[1] > info1[0]{
intervals[i][1] = min(intervals[i-1][1], intervals[i][1])
res++
}
}
return res
}
func min(i, j int)int{
if i>j{
return j
}else{
return i
}
}
题目三
代码与解析
这道题和上面两道也很像,
上面两道是更新最小右边界
这道题是更新最大右边界,并顺势去掉不符合的数组
详解可以看下面代码注释或者carl博客
这里的关键也是 判断左右边界大小和
更新边界points[i][1] = min(points[i-1][1], points[i][1])
另外索引i要– 否则索引越界
func merge(intervals [][]int) [][]int {
//先从小到大排序
sort.Slice(intervals,func(i,j int)bool{
return intervals[i][0]<intervals[j][0]
})
//再弄重复的
for i:=0;i<len(intervals)-1;i++{
// 当前右边界intervals[i][1]和下一区间左边界intervals[i+1][0]比较
// 这种情况相当于[1,4] [2,5]
if intervals[i][1]>=intervals[i+1][0]{
// 更新区间右边界最大值
intervals[i][1]=max(intervals[i][1],intervals[i+1][1])//赋值最大值
// 删除下一个区间元素,因为此时当前区间右边界已经变了
intervals=append(intervals[:i+1],intervals[i+2:]...)
i--
}
}
return intervals
}
func max(a,b int)int{
if a>b{
return a
}
return b
}