大廠面試真題詳解：合并區間

給出若幹閉合區間，合并所有重疊的部分。

線上評測位址：

領扣題庫官網 樣例1:

輸入: [(1,3)]
輸出: [(1,3)]           

樣例 2:

輸入:  [(1,3),(2,6),(8,10),(15,18)]
輸出: [(1,6),(8,10),(15,18)]           

解題思路

對應兩個區間a, b，如何判斷它們相交？

當a, b滿足max(a.start,b.start)<=min(a.end,b.end)max(a.start,b.start)<=min(a.end,b.end)時，兩者相交。

我們應考慮某種排序方式，使得所有相交的區間對應一段連續的數組下标，這樣友善我們進行之後的合并操作。

這種排序方式應該是對區間的左端點按從小到大的方式進行排序，假設我們存在一個已經按照上面方式排序的數組：1，22，46，10。

可以看出，當我周遊數組的時候，每次通路一個區間ai，都能保證：如果ai和它前面的區間不相交，那麼ai後面的任意區間都不能和ai前面的任意區間相交。這樣就保證了時間複雜度為O(n)級别，即不會出現其他的周遊。

比如區間[5，7]，他和前面的區間都沒有相交，他後面的所有區間和它一樣，沒有和[5，7]前面的區間有交集。

代碼思路

1. 對區間數組按區間的左端點start排序。
2. 将最後的區間指派lastinterval為intervals[0]。
3. 周遊輸入，如果lastinterval和目前區間相交，合并兩個區間。
4. 如果不相交，将lastinterval加入結果，并将lastinterval指派為目前的區間。

複雜度分析

設區間的個數為N。

時間複雜度

• 排序的時間複雜度為O(NlogN)。
• 周遊一遍數組的時間複雜度為O(N)。

• 總時間複雜度為O(NlogN)。

  空間複雜度

• 空間複雜度為O(n)，可能存在每一個區間都不與任何一段區間相交，傳回的答案和傳入的參數長度相等。

public class Solution {
    /**
     * @param intervals: interval list.
     * @return: A new interval list.
     */
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() == 0) {
            return intervals;
        }
        
        // 根據區間的start值排序
        intervals.sort(Comparator.comparing(i -> i.start));
        
        List<Interval> result = new ArrayList<Interval>();
        Interval lastInterval = intervals.get(0);
        
        // 如果兩段區間有交集的話，合并兩段區間
        // 沒有的話，将最後的區間加入答案，并令新的區間作為最後的區間
        for (Interval interval: intervals) {
            if (haveIntercation(lastInterval, interval)) {
                lastInterval = mergeTwoIntervals(lastInterval, interval);
            }
            else {
                result.add(lastInterval);
                lastInterval = interval;
            }
        }
        result.add(lastInterval);
        
        return result;
    }
    // 合并兩段區間
    private Interval mergeTwoIntervals(Interval a, Interval b) {
        return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));
    }
    // 判斷區間是否有交集，要滿足較大的start小于等于較小的end
    private boolean haveIntercation(Interval a, Interval b) {
        return Math.max(a.start, b.start) <= Math.min(a.end, b.end);
    }
}           

更多題解參考： 九章官網Solution