57. Insert Interval 插入区间

题目

给定一个不重叠的区间组 intervals。这个区间按照 start[i] 升序排列。然后给定一个新区间 newInterval 。
要求将这个区间按照原来的规则插入，使新形成的区间符合原来的规则，必要的时候应该进行区间合并。

解析

以 [1,2] [3,5] [6,7] [8,10] [12,16] 新 [4,8] 为例

1. 判断新区间和当前区间是否重叠，利用 end < start[i] || start > end[i]，如果不重叠，则递进。
2. 如果重叠，合成区间的头 = min（start，start[i]）
3. 获取尾部覆盖，判断新区间的尾是否覆盖当前区间，如果覆盖，继续向下判断，直到不覆盖位置。当不覆盖的时候，尾 = start[i]

伪代码

for i < len
  // 判断头
  if new[end] < ints[i][start]
    rst+=new
    rst+=ints[i]...
    break
  if new[start] > ints[i][end]
    rst+=ints[i]
    if i == len-1
      rst+=new
      return
// 重叠，处理重叠情况，步进到一个不覆盖的区域
head = min(ints[i][start], new[start])
for i < len && new[end] > ints[i][end]
  i++
if i == len
  tail = new[end]
else
  if new[end] < ints[i][start]
    i++
    tail = new[end]
  else new[end] <= ints[i][end]
    tail = ints[i][end]
rst+=[]int{head,tail}
for i< len
  rst+=ints[i]
return

代码

func insert(intervals [][]int, newInterval []int) [][]int {
    start,end := 0,1
    var i int
    var rst [][]int
    for ;i<len(intervals);i++ {
        if newInterval[end] < intervals[i][start] {
            rst=append(rst, newInterval)
            rst=append(rst, intervals[i:]...)
            return rst
        }
        if newInterval[start] > intervals[i][end] {
            rst=append(rst, intervals[i])
            continue
        }
        break
    }
    if i == len(intervals) {
        rst=append(rst, newInterval)
        return rst
    }
    head:=newInterval[start]
    if head > intervals[i][start] {
        head = intervals[i][start]
    }
    for i<len(intervals) && newInterval[end] > intervals[i][end] {
        i++
    }
    if i == len(intervals) {
        rst=append(rst, []int{head,newInterval[end]})
        return rst
    }
    if newInterval[end] < intervals[i][start] {
        rst=append(rst, []int{head,newInterval[end]})
    }else {
        rst=append(rst, []int{head,intervals[i][end]})
        i++
    }
    rst=append(rst, intervals[i:]...)
    return rst
}