题目一

leetcode:452

代码与解析

给定二维空间， 一个二维数组
[[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
    }
}

题目二

leetcode:435

代码与解析

这道题和上一道题有异曲同工之妙，
这个也是判断左右区间
甚至比上一道简单，只需要找到相应区间，

上一道是找到不重合的左右边界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
    }
}

题目三

leetcode:56

代码与解析

这道题和上面两道也很像，
上面两道是更新最小右边界
这道题是更新最大右边界，并顺势去掉不符合的数组
详解可以看下面代码注释或者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
}