題目
#

leetcode 56 - Merge Intervals (題目說明請點連結)

題目簡述
#

給一個區間陣列 intervals，其中 intervals[i] = [starti, endi]。
合併所有重疊的區間，並返回一個不重疊的區間陣列，該陣列恰好覆蓋輸入中的所有區間。

範例
#

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: 區間 [1,3] 和 [2,6] 重疊，合併為 [1,6]。

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: 區間 [1,4] 和 [4,5] 重疊，合併為 [1,5]。

解題思路
#

這題要求我們合併所有重疊的區間。我們可以使用排序和貪心算法來解決這個問題，先按照區間的起始位置排序，然後遍歷排序後的區間，合併重疊的區間。

解法
#

排序 + 貪心

如果區間陣列長度小於等於 1，直接返回原陣列
按照區間的起始位置對陣列進行排序
創建一個結果列表，用於存儲合併後的區間
遍歷排序後的區間：
- 如果結果列表為空或當前區間與最後一個區間不重疊，直接加入
- 如果重疊，則合併區間（更新最後一個區間的結束位置）
返回合併後的結果

步驟
#

邊界檢查：
- 如果 intervals.length <= 1，直接返回原陣列
排序：
- 按照區間的起始位置 a[0] 進行排序
合併區間：
- 遍歷排序後的區間
- 檢查是否與最後一個區間重疊
- 如果不重疊，加入結果列表
- 如果重疊，合併區間
返回結果：
- 將結果列表轉換為陣列並返回

例子說明
#

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

步驟	當前區間	結果列表	操作說明
排序後	[[1,3],[2,6],[8,10],[15,18]]	[]	按起始位置排序
i=0	[1,3]	[[1,3]]	結果列表為空，直接加入
i=1	[2,6]	[[1,6]]	與 [1,3] 重疊，合併為 [1,6]
i=2	[8,10]	[[1,6],[8,10]]	與 [1,6] 不重疊，直接加入
i=3	[15,18]	[[1,6],[8,10],[15,18]]	與 [8,10] 不重疊，直接加入

最終結果： [[1,6],[8,10],[15,18]]

合併說明：

[1,3] 和 [2,6] 重疊，合併為 [1,6]
[8,10] 和 [15,18] 不重疊，保持原樣

完整程式碼
#

java

class Solution {
    public int[][] merge(int[][] intervals) {
        // 如果區間陣列長度小於等於 1，直接返回
        if (intervals.length <= 1) {
            return intervals;
        }

        List<int[]> merge = new ArrayList<>();
        // 按照區間的起始位置排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        for (int[] interval : intervals) {
            // 如果結果列表為空或當前區間與最後一個區間不重疊
            if (merge.isEmpty() || merge.get(merge.size() - 1)[1] < interval[0]) {
                merge.add(interval);
            } else {
                // 合併重疊的區間，更新最後一個區間的結束位置
                merge.get(merge.size() - 1)[1] = Math.max(merge.get(merge.size() - 1)[1], interval[1]);
            }
        }

        // 將結果列表轉換為陣列並返回
        return merge.toArray(new int[merge.size()][]);
    }
}