57. Insert Interval
這題的解法很簡單，直接把新的區間加入進去，重新使用 56. 題的解法。
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
intervals.append(newInterval)
intervals.sort()
stack = [intervals[0]]
for i in range(1, len(intervals)):
prevInterval = stack.pop()
newInterval = intervals[i]
if prevInterval[1] >= newInterval[0]:
newInterval = [min(prevInterval[0], newInterval[0]), max(prevInterval[1], newInterval[1])]
else:
stack.append(prevInterval)
stack.append(newInterval)
return stack
其實這樣的時間複雜度已經滿不錯的，就是 O(N log N) ，主要的時間會花在排序上面，但是這個題目給定的條件，和前面幾題不一樣，那就是給的時間表，早就已經排序過了。所以如果說直接加入到最後面，用 sort 排序的話，是很沒有效率的，雖然 LeetCode是給過的。
解法很簡單，直接找到哪裡需要插入，插入到那個位置就好。
這樣整個題目的時間複雜度就會在 O(N) 。
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
new_intervals = []
insertIndex = len(intervals)
for i in range(len(intervals)):
if intervals[i][0] > newInterval[0]:
insertIndex = i
break
intervals.insert(insertIndex, newInterval)
stack = [intervals[0]]
for i in range(1, len(intervals)):
prevInterval = stack.pop()
newInterval = intervals[i]
if prevInterval[1] >= newInterval[0]:
newInterval = [min(prevInterval[0], newInterval[0]), max(prevInterval[1], newInterval[1])]
else:
stack.append(prevInterval)
stack.append(newInterval)
return stack