Leetcode — 56. Merge Intervals (中文)

問題連結: https://leetcode.com/problems/merge-intervals/

給予一個二維陣列intervals , 每個intervals[i] 長度皆為2, 包含一個起始點跟終點
求把所有重疊的intervals 併在一起
最後回傳把intervals合併後的新陣列

例子:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]] 
因為[1,3]與[2,6]重疊 可以併為[1,6] 

想法:

我們需要先想 要如何判斷兩個intervals有沒有重疊
假設我們有interval A與interval B, 當interval B的起點 比 interval A 的終點還大的時候, 代表我們可以放心的把他們視為兩個不重疊的intervals
反之亦然, 若B的起點開始的比A終點早的話, 代表他們兩者就會重疊了
所以我們可以利用這個邏輯來判斷 我們要不要merge 這些intervals

⚠️因為不保證intervals一定是按照起點排序的, 因此我們先需要保證陣列有先排序好, 我們再做之後動作

程式邏輯:

先確定intervals陣列是依照起點排序後, 就可以開始我們的程式了
首先我們用兩個變數來儲存現階段我們拿到的start及end
再迴圈中, 我們來比較我們手上的end 以及迴圈當下位置的start 的值來判斷要不要合併他們
若可以合併, 更新手上的end, 取比較大的end當作手上新的end
若不能合併, 則直接把手上的start跟end存進list中, 再把當下位置的start和end當作手上的變數

迴圈結束後別忘記再把手上的start及end放進list 就完成了

以下為我的 5ms 程式碼, 贏過94%的人:

public int[][] merge(int[][] intervals) {
        if(intervals.length<=1)
            return intervals;
        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] i1,int[] i2){
                return i1[0]-i2[0];
            }
        });
        int prevStart = intervals[0][0];
        int prevEnd = intervals[0][1];
        List<int[]> list = new ArrayList<>();
        for(int i = 1; i < intervals.length; i++)
        {
            int curStart = intervals[i][0];
            int curEnd = intervals[i][1];
            if(curStart <= prevEnd) //merge
                prevEnd = Math.max(prevEnd,curEnd);
            else
            {
                list.add(new int[]{prevStart,prevEnd});
                prevStart = curStart;
                prevEnd = curEnd;
            }
        }
        list.add(new int[]{prevStart,prevEnd});
        int[][] rst = new int[list.size()][];
        for(int i=0;i<rst.length;i++)
            rst[i] = list.get(i);
        
        return rst;
    }

若不包含最一開始陣列排序的部分, 時間跟空間複雜度為O(n)
整個程式碼的時間複雜度則是O(nlogn) (亦即Arrays.sort()的時間)