#57. Insert Interval

題目描述

給你一個沒有重疊的區間並且以區間起點start_i做升序排列的陣列intervals，區間範圍表示為intervals[i] = [start_i, end_i]。
同時也給你一個新的區間newInterval = [start, end]。

將新區間newInterval插入intervals並保持區間陣列的升序排列以及沒有重疊區間的存在，如果有必要可以合併重疊的區間。

插入完畢後回傳intervals。

限制條件

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i <= end_i <= 10^5
intervals以區間起點start_i為基準做升序排列。
newInterval.length == 2
0 <= start <= end <= 10⁵

解題思路

這一題主要有兩個動作需要我們處理，插入和合併，插入是題目的要求，合併是可能會發生的事情，不論哪一個都會對陣列長度造成影響，所以比較好的方式是把區間陣列和新的區間合併到一個新的陣列之中。

Solution

首先創造一個新的陣列並且將要插入的區間放進去。
接下來把區間陣列中的區間一一放入新陣列中，主要會遇上以下三種狀況。
狀況1：要放入的區間比新陣列尾端的區間還要前面，這個狀況只要將兩個區間的值互換之後，再把還在外面的區間放入就可以保持順序的一致。
狀況2：要放入的區間在新區間的後面，這個狀況順序是OK的也沒有重疊，直接放入即可。
狀況3：如果不是前後順序這兩種狀況，那麼就是重疊了，重疊只要將新陣列尾端的區間值跟重疊的值合併起來就可以了。

public class Solution { 
	public int[][] Insert(int[][] intervals, int[] newInterval) {
        List<int[]> ans = new List<int[]>();
        ans.Add(newInterval);        
        foreach(int[] i in intervals){
            int tail = ans.Count-1;
            if(i[1]<ans[tail][0]){
                int[] tmp = ans[tail];
                ans[tail] = i;
                ans.Add(tmp);
            }else if(i[0]>ans[tail][1]){
                ans.Add(i);
            }else{
                ans[tail][0] = Math.Min(ans[tail][0],i[0]);
                ans[tail][1] = Math.Max(ans[tail][1],i[1]);
            }
        }
        return ans.ToArray();
    }
}

複雜度分析：

時間複雜度：時間複雜度為O(n)。
空間複雜度：空間複雜度為O(n)。

學習重點

陣列