這一題是昨天題目的延伸，給定一個沒有重疊且已經排序過區段的陣列，然後要將一個新區段加入此陣列，並且保持新的陣列仍然沒有重疊且排序過．

題目

You are given an array of non-overlapping intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

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

Constraints:

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 105

提示

Python

談到插入元素到已排序過的陣列，最直覺的方法就是從頭比對找到合適的位置後插入元素，或插入後再次排序整個陣列。但隨著陣列越來越長，將會越來越慢，甚至造成大量不必要的運算，這時可以利用 Python 內建模組 bisect ，透過一個基礎的 bisection 演算法幫我們插入元素到一個已經排序過的串列之中，如此一來該串列就不需要在新增元素後重新進行排序。

bisect.insort(a, x, lo=0, hi=len(a), *, key=None) 涵式會直接插入元素 x 到陣列 a 之中
如果 a 裡面已經有 x 出現，插入的位置會在所有 x 的後面，此函式整體時間複雜度是 O(n)。

Go

Go 沒有 bisec. 然而我們可以使用 sort.Search(n int, f func(int) bool) 去找出正確的 index 位置， 然後再將元素插入到對應的 index 位置，已達到相同的結果．

例如：

func insert(a []int, index int, value int) []int {
    if len(a) == index { // nil or empty slice or after last element
        return append(a, value)
    }
    a = append(a[:index+1], a[index:]...) // index < len(a)
    a[index] = value
    return a
}

我的答案

先將新區段插入陣列中適當的位置以保持排序，然後在用昨天的演算法把重疊的部分合併。

方法1: 插入新區段後再次排序整個陣列

Python

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        intervals.append(newInterval)
        intervals.sort(key=lambda x: x[0])
        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

方法2: 使用 bisect 插入新區段到已排序的陣列中

Python

from bisect import insort
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        insort(intervals,newInterval)
        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

Go

import (
    "fmt"
    "math"
)

func insortInterval(a [][]int, index int, value []int) [][]int {
    if len(a) == index { // nil or empty slice or after last element
        return append(a, value)
    }
    a = append(a[:index+1], a[index:]...) // index < len(a)
    a[index] = value
    return a
}

func insert(intervals [][]int, newInterval []int) [][]int {
    i := sort.Search(len(intervals), func(i int) bool { return intervals[i][0] >= newInterval[0] })
    intervals = insortInterval(intervals, i, newInterval)
    merged := [][]int{}
    for _, interval := range intervals {
        n := len(merged)
        if n == 0 || merged[n-1][1] < interval[0] {
            merged = append(merged, interval)
        } else {
            merged[n-1][1] = int(math.Max(float64(merged[n-1][1]), float64(interval[1])))
        }
    }
    return merged
}