LeetCode(12) 插入区间

xbdyhh · · 321 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

题目：

给出一个无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

思路：

首先进行分析，可以发现区间分为三种，一种是在插入区间左侧的，即右区间小于需插入区间左区间的，一种是在插入区间右侧的，即左区间大于插入区间右区间的，以上两种直接插入新区间集合即可，最后一种是和需插入区间有交集的，这种需要做合并。接下来为代码实现：

func insert(intervals [][]int, newInterval []int) [][]int {
   left,right := newInterval[0],newInterval[1]
   var isInserted = false//用于判断区间是否被插入了，false为尚未插入，true为已经插入完成
 var ans [][]int
 //1.从左向右读取区间，如果与区间不相交直接插入
 //2.如果和区间相交更新区间的值，继续判断
 //3，如果读取完，或者读取到第一个与区间不相交的值，插入区间
 //4，插入后的区间直接插入新数组
 for _,val := range intervals{
      if isInserted{
         ans = append(ans,val)
         continue
 }
      if val[0]>right && !isInserted{
         ans = append(ans,[]int{left,right})
         isInserted = true
 ans = append(ans,val)
         continue
 }
      if val[1]<left && !isInserted{
         ans = append(ans,val)
         continue
 }
      left = min(left,val[0])
      right = max(right,val[1])
   }
   if !isInserted{ans = append(ans,[]int{left,right})}
   return ans
}
func max(x,y int)int{
   if x>y{
      return x
   }
   return y
}
func min(x,y int)int{
   if x<y{
      return x
   }
   return y
}