區間應用: 插入新的區間 Insert Interval_Leetcode #57

Markus Spiske on Unsplash

題目敘述

題目會給定我們一個已經根據起點升序排列好的輸入陣列 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~十萬之間。

• intervals is sorted by starti in 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:

[1] Insert Interval - LeetCode