数据结构和算法-区间问题

区间问题

• 无重叠区间

  给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
  注意:
  可以认为区间的终点总是大于它的起点。
  区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠

• 合并区间

  以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

合并区间

要解答合并区间，可以理解为求并集，同样还是对区间数组排序，然后选基准区间迭代，如果基准区间的闭区间大于当前的区间的开区间，那么就更新基准区间的闭区间为当前区间的闭区间，反之当前的基准区间就是我们要的结果的子集，所以把基准区间添加到结果集中，重新设置基准区间，直到数组结束。

解题思路

代码实现

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
    ans:=make([][]int,0)
    left,right:=intervals[0][0],intervals[0][1]
    for i:=1;i<len(intervals);i++{
        if right>=intervals[i][0]{
            right=max(right, intervals[i][1])
        }else{
            ans=append(ans,[]int{left,right})
            left, right = intervals[i][0], intervals[i][1]
        }
    }
     ans=append(ans,[]int{left,right})
     return ans
    
}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

无重叠区间

解题思路

要实现无重叠的区域，可以理解为求交集，排除相交区间就是不重叠区间，同样还是对区间数组排序，然后选基准区间迭代，判断当前区间的开区间是否与基准区间相交，如果不相交则替换基准区间的闭区间同时统计不相交区间的个数，最终的答案就是用整个数组的长度减去不相交的区间个数。

代码实现

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals,func(i,j int)bool{
        return intervals[i][1] <intervals[j][1]
    })
    count:=1
    end:=intervals[0][1]
    for _,p:=range intervals{
        if p[0]>=end{
            count++
            end= p[1]
        }
    }
    return len(intervals)-count
}