## Array - 57. Insert Interval

Updated on with 0 views and 0 comments
1. 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.

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))
}
*/
``````