Note: cool hard problem :)
(intervals [][]int, newInterval []int)
| 6 | |
| 7 | // Note: cool hard problem :) |
| 8 | func insert(intervals [][]int, newInterval []int) [][]int { |
| 9 | if len(intervals) == 0 { |
| 10 | return [][]int{newInterval} |
| 11 | } |
| 12 | |
| 13 | merged := make([][]int, 0) |
| 14 | |
| 15 | // discard all non-overlapping intervals by placing them into merged |
| 16 | i := 0 |
| 17 | for i < len(intervals) { |
| 18 | if intervals[i][1] < newInterval[0] { |
| 19 | merged = append(merged, intervals[i]) |
| 20 | } else { |
| 21 | break |
| 22 | } |
| 23 | |
| 24 | i++ |
| 25 | } |
| 26 | |
| 27 | // 0: did not find an interval where new interval start is less than i-th interval end |
| 28 | if i == len(intervals) { |
| 29 | return append(merged, newInterval) |
| 30 | } |
| 31 | |
| 32 | // 1: interval doesn't merge at all |
| 33 | if newInterval[0] < intervals[i][0] && newInterval[1] < intervals[i][0] { |
| 34 | return append(append(merged, newInterval), intervals[i:]...) |
| 35 | } |
| 36 | |
| 37 | // the minimum merged value is the new interval start or the i-th interval start |
| 38 | minMerged := int(math.Min(float64(newInterval[0]), float64(intervals[i][0]))) |
| 39 | |
| 40 | // 2: the new interval end is between the i-th start and end inclusive |
| 41 | if newInterval[1] >= intervals[i][0] && newInterval[1] <= intervals[i][1] { |
| 42 | maxMerged := intervals[i][1] |
| 43 | merged = append(merged, []int{minMerged, maxMerged}) |
| 44 | i++ |
| 45 | } else { |
| 46 | // 3: the new interval end could span many intervals |
| 47 | maxMerged := -1 |
| 48 | i++ |
| 49 | for i < len(intervals) { |
| 50 | if newInterval[1] < intervals[i][0] { |
| 51 | maxMerged = newInterval[1] |
| 52 | break |
| 53 | } else if newInterval[1] >= intervals[i][0] && newInterval[1] <= intervals[i][1] { |
| 54 | // if new interval end falls in between an interval |
| 55 | maxMerged = intervals[i][1] |
| 56 | i++ |
| 57 | break |
| 58 | } |
| 59 | |
| 60 | i++ |
| 61 | } |
| 62 | |
| 63 | // new interval end is larger than all other intervals |
| 64 | if maxMerged == -1 { |
| 65 | maxMerged = newInterval[1] |