題目敘述
題目會給定我們一個已經根據起點升序排列好的輸入陣列 intervals，裡面的每個pair分別代表每個區間的起點和終點。
接下來新插入一個區間newInterval，插入後如果和原本的區間重疊，請把他們合併，
要求我們輸出插入後的結果。
題目的原文敘述
測試範例
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
新插入的[2, 5]和[1, 3]有重疊，合併為[1, 5]
所以插入後的結果為
[[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].
新插入的[4, 8]和[3, 5], [6, 7], [8, 10]有重疊，合併為[3, 10]
所以插入後的結果為
[[1,2],[3,10],[12,16]]
約束條件
Constraints:
0 <= intervals.length <= 10^4
輸入陣列的長度介於0~一萬。
intervals[i].length == 2
輸入陣列內的每個元素都是一組pair，分別代表區間起點和終點。
0 <= starti<= endi<= 10^5
起點和終點都介於0~十萬之間。
intervalsis sorted bystartiin ascending order.
輸入陣列已經根據起點做好升序排列。
newInterval.length == 2
新插入的區間也是一組pair，分別代表區間起點和終點。
0 <= start <= end <= 10^5
起點和終點都介於0~十萬之間。
演算法 掃描與合併
題目已經給了我們一個很強的條件:
輸入的區間都已經依照起點位置排序好。
那麼，我們接著只要依序掃描每一個區間，檢查新插入的區間和當下的區間i有沒有重疊?
如果有重疊，合併並且計算擴張後的新起點和新終點。
如果沒有重疊，依照區間i的起點終點位置判斷在新區間的左邊還是右邊。
把區間i放在新區間的左手邊或者右手邊即可。
程式碼 掃描與合併
class Solution:
def insert(self, intervals, newInterval):
# Constant to help us access start point and end point of interval
START, END = 0, 1
s, e = newInterval[START], newInterval[END]
left, right = [], []
for cur_interval in intervals:
if cur_interval[END] < s:
# current interval is on the left-hand side of newInterval
left += [ cur_interval ]
elif cur_interval[START] > e:
# current interval is on the right-hand side of newInterval
right += [ cur_interval ]
else:
# current interval has overlap with newInterval
# merge and update boundary
s = min(s, cur_interval[START])
e = max(e, cur_interval[END])
return left + [ [s, e] ] + right
複雜度分析 掃描與合併
時間複雜度: 一個線性掃苗，所需時間為O(n)
空間複雜度: 一個新的陣列，存放合併、排序好的所有區間，陣列長度最大為O(n)。
關鍵知識點
題目已經幫我們排序好區間順序，
我們只要接著依序檢查區間、(假如有重疊的話)合併區間即可。
Reference:
