Array - 57. Insert Interval

57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = `[[1,2],[3,5],[6,7],[8,10],[12,16]]`, newInterval = `[4,8]`
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval `[4,8]` overlaps with `[3,5],[6,7],[8,10]`.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

思路：

题目意思是将一个区间插入一个有序的区间集合，做法有两种:
方法1. 参考第56题，在这题目中，只需要把待插入的区间插入到有序集合之中，就变成56题合并区间的题目。
方法2. 可以把区间集合看做三个部分：与插入无关的左边区间集合 | 与插入区间有关的集合 | 与插入无关的右边区间集合，这样区分之后，在插入区间有关的集合中，只需要更新上下界限就可以。

代码：

go：

// solution one:
func insert(intervals [][]int, newInterval []int) [][]int {
    start, end := newInterval[0], newInterval[1]
    left, right := make([][]int, 0), make([][]int, 0)
    
    for _, interval := range intervals {
        if interval[1] < start {
            // 左边区间集合
            left = append(left, interval)
        } else if interval[0] > end {
            // 右边区间集合
            right = append(right, interval)
        } else {
            if interval[0] < start {
                start = interval[0]
            }
            if interval[1] > end {
                end = interval[1]
            }
        }
    }
    
    left = append(left, []int{start, end})
    left = append(left, right...)
    
    return left
}


// solution two:
/*
type myInterval [][]int

func (intervals myInterval)Len() int { return len(intervals) }
func (intervals myInterval)Less(i, j int) bool { return intervals[i][0] < intervals[j][0] } 
func (intervals myInterval)Swap(i, j int) {
    intervals[i], intervals[j] = intervals[j], intervals[i]
}
func (intervals myInterval)back() []int {
    return intervals[len(intervals) - 1]
}
func (intervals *myInterval)pushBack(interval []int) {
    *intervals = append(*intervals, interval)
}
func (intervals *myInterval)modifyBack(i, j int) {
    if i > j {
        (*intervals)[len(*intervals) - 1][1] = i
    } else {
        (*intervals)[len(*intervals) - 1][1] = j
    }
}


func merge(intervals myInterval) [][]int {
    var res myInterval
    
    for _, interval := range intervals {
        if len(res) == 0 || interval[0] > res.back()[1] {
            res.pushBack(interval)
        } else {
            // merge
            res.modifyBack(interval[1], res.back()[1])
        }
    }
    
    return res
}

func insert(intervals myInterval, newInterval []int) [][]int {
    if intervals.Len() == 0 {
        return append([][]int{}, newInterval)
    }
    
    for i := 0; i <= intervals.Len() - 1; i++ {
        if newInterval[0] <= intervals[i][0] {
             nums := append([][]int{}, intervals[:i]...)
             nums = append(nums, newInterval)
             nums = append(nums, intervals[i:]...)
             return merge(nums)
        }
    }
    
    return merge(append(intervals, newInterval))
}
*/