## Description

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].
``````

## Solution

• 先找出所有比新区间小的区间
• 再找出所有比新区间大的区间
• 在查找过程中将新区间与相邻区间合并
• 最后返回`[小区间]`+`[新区间]`+`[大区间]`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 `````` ``````func insert(intervals []Interval, newInterval Interval) []Interval { length := len(intervals) if length == 0 { return []Interval{newInterval} } // 分割比 newInterval 小的区间 lEnd := 0 for lEnd < length && newInterval.Start > intervals[lEnd].End { lEnd++ } // 边界判断 if lEnd == length { return append(intervals, newInterval) } if intervals[lEnd].Start < newInterval.Start { // 将当前区间与 newInterval 合并 newInterval.Start = intervals[lEnd].Start } // 分割比 newInterval 大的区间 rStart := lEnd for rStart < length && newInterval.End >= intervals[rStart].Start { if intervals[rStart].End > newInterval.End { // 将当前区间与 newInterval 合并 newInterval.End = intervals[rStart].End } rStart++ } // append 时用 newInterval 建立新的 Slice 与 intervals[rStart:] 合并 // 再与 intervals[:lEnd] 合并 // 之前直接将 newInterval append 到 intervals[:lEnd] 后面，再与 intervals[rStart:] 合并 // 会导致 intervals[rStart:] 的内存区域被覆盖 return append(intervals[:lEnd], append([]Interval{newInterval}, intervals[rStart:]...)...) }``````