#56. Merge Intervals

題目描述

給你一個陣列intervals，intervals[i] = [starti, endi]，合併所有重疊的區間，並且回傳一個沒有任何重疊區間的陣列。

限制條件

1. 1 <= intervals.length <= 10⁴
2. intervals[i].length == 2
3. 0 <= starti <= endi <= 10⁴

解題思路

這一題並沒有要求in-place的操作，因此我們可以直接創造一個新的空間來放置合併後的區間。

執行步驟：

1. 由於這一題並沒有描述說區間是按照順序排列的，因此要先對區間陣列進行整理。
2. 接著開始將區間一一放入答案空間。
   1. 如果答案空間長度為0，代表沒有放置任何區間，無法進行比較，因此先將第一個區間放入。
   2. 比較當前的區間和答案陣列中的最後一個區間，如果有重疊就合併，沒有就直接放入。
3. 完成合併。

public class Solution {    
    public int[][] Merge(int[][] intervals) {
        Array.Sort(intervals, (x,y)=> x[0].CompareTo(y[0]));
        var ans = new List<int[]>();
        foreach(var interval in intervals){
            if(ans.Count==0){
                ans.Add(interval);
                continue;
            }
            int last = ans.Count-1;
            if(interval[0] <= ans[last][1]){
                ans[last][0] = Math.Min(ans[last][0],interval[0]);
                ans[last][1] = Math.Max(ans[last][1],interval[1]);
            }else{
                ans.Add(interval);
            }
        }
        return ans.ToArray();
    }
}

複雜度分析：

• 時間複雜度：由於呼叫了Sort()函式，所以時間複雜度會是O(n logn)。
• 空間複雜度：答案不算入使用空間的話，空間複雜度為O(1)。

學習重點

• Sorting