###### tags: `Leetcode` `medium` `array` `python`

# 57. Insert Interval

## [題目連結:] https://leetcode.com/problems/insert-interval/

## 題目:
You are given an array of non-overlapping intervals ```intervals``` where ```intervals[i] = [starti, endi]``` represent the start and the end of the ```ith``` interval and ```intervals``` is sorted in ascending order by ```start i```. 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 ```start i``` 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].

## 解題想法:
兄弟題目: [56. Merge Intervals](/EWcn2omYSMK8guHGNxjBPA)
* 此題給的間格[start,end]，均已按照start由小到大排好
* 給一新的間格newIterval插入數組，將重疊區合併
* 因為已經排序好，可將整體數組視為:
* **前半段安全區**+**中間需調整區**+**後半段安全區**
* 前半段安全區:
* while迴圈: 若當前間格的end比newIterval的start還小，
* 表示並未重疊，可直接加入res
* 中間需調整區:
* 進來此區域，表示當前的間格的end已經大於newIterval的start了(重疊)
* newIterval插入後更新中間重疊區
* new_start=newIterval[0]
* new_end=newItervals[1]
* while迴圈: **若當前間格的start比new_end小**:
* 調整new_start，取更小的(靠左邊)
* min(new_start,當前間格start)
* 調整new_end，取更大的(靠右邊)
* max(new_end,當前間格end)
* 將此[new_start,start_end]加入res
* 後半段安全區:
* 直接將後半段加入res即可

* 示意圖:

            4~~~~~~~~~8
    1~2    3~~5  6~7  8~~10  12~~~16
    
step1: 找前半段完全沒相交的 1~2 直接放結果中
step2: 當前區間的右端點(3~5之中的5)大於等於新區間左端點4且小於其右端點8
        ->合併 將4~8更新為3~8 .........直到為3~10
step3: 直到沒相交了 12~16 把後段放入結果 
final: [[1,2],[3,10],[12,16]]

## Python(Sol1): time:O(n)

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        # time:O(n)
        if len(intervals)==0:
            return [newInterval]
        cur_pos=0
        res=[]
        #前半段安全區: 當前尾<新頭
        while cur_pos<len(intervals) and intervals[cur_pos][1]<newInterval[0]:
            res.append(intervals[cur_pos])
            cur_pos+=1
        #處理中間需調整區: 正常重疊，當前的頭仍小於新的尾
        new_start=newInterval[0]
        new_end=newInterval[1]
        while cur_pos<len(intervals) and intervals[cur_pos][0]<=new_end:
            new_start=min(new_start,intervals[cur_pos][0])
            new_end=max(new_end,intervals[cur_pos][1])
            cur_pos+=1
        res.append([new_start,new_end])
        #後半段安全區
        res.extend(intervals[cur_pos:])
        return res

if __name__ == '__main__':
    result = Solution()
    intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
    newInterval = [4,8]
    ans = result.insert(intervals,newInterval)
    print(ans)

## Python(Sol2): time: O(NlogN)
相當於[56. Merge Intervals](/EWcn2omYSMK8guHGNxjBPA)
將新的間格加入，重排序，處理重疊

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        intervals.append(newInterval)
        intervals.sort(key = lambda x:x[0])
        ans = [intervals[0]]
        for cur_item in intervals[1:]:
            if ans[-1][1]>=cur_item[0]:
                ans[-1][1] = max(ans[-1][1],cur_item[1])
            else:
                ans.append(cur_item)
        return ans