【LeetCode教學】56. Merge Intervals

給定一個區間數組，合併所有重疊區間。

題目連結：連結點此。

題目描述

給定一個區間數組，其中 intervals[i] = [start_i, end_i]，合併所有重疊區間，並傳回一個覆蓋輸入中所有區間的非重疊區間數組。

題目限制

1 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁴

解題方法

1. 先宣告一個用於儲存結果的變數output。

vector<vector<int>> result;

2. 因為 intervals 未排序，所以先將按照intervals每個區間的起始時間由小到大排序。

sort(intervals.begin(), intervals.end());

3. 遍歷每個區間：

for (vector<int> interval : intervals)

3-1. 如果result還沒有任何區間或是當前區間和result的最後一個區間沒有關聯，就直接加入result。

if (result.empty() == true ||
    interval[1] < result.back()[0] || 
    interval[0] > result.back()[1]) 
{
    result.push_back(interval);
}

3-2. 如果當前區間和result的最後一個區間有關聯，就更新result的最後一個區間的結束時間（因為區間的起始時間已經排序過）。

else
{
    result.back()[1] = max(result.back()[1], interval[1]);
}

完整程式碼

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {

        //1.宣告變數
        vector<vector<int>> result;
        
        //2.將輸入的區間按照起始時間由小到大排序
        sort(intervals.begin(), intervals.end());

        //3.遍歷每個區間
        for (vector<int> interval : intervals)
        {
            //3-1.
            if (result.empty() == true ||  //如果result還沒有任何區間
                interval[1] < result.back()[0] ||  //當前區間比result的最後一個區間還要小
                interval[0] > result.back()[1])  //當前區間比result的最後一個區間還要大
            {
                result.push_back(interval);
            }
            //3-2.
            else  //當前區間和result的最後一個區間有相關
            {
                //因為區間的起始時間已經排序過，所以此處更新結束時間即可
                result.back()[1] = max(result.back()[1], interval[1]);
            }
        }

        return result;
    }
};

測試資料

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]

Input: intervals = [[1,4],[2,3]]
Output: [[1,4]]

此題目的輸入intervals不會為空，所以應該是沒有太特別的edge case要考慮。

時間與空間複雜度

時間複雜度：O(n log n)，排序需要 O(n log n)，遍歷 intervals 一次需要 O(n)。

空間複雜度：O(n)，用於儲存結果陣列。

其他相關題目

57. Insert Interval