題目說明
LeetCode 56. Merge Intervals
給一組區間 intervals，每個區間是 [start, end]，可能有重疊部分。
請合併所有重疊的區間，並回傳合併後的區間集合。

範例

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
解釋：區間 [1,3] 和 [2,6] 重疊，所以合併成 [1,6]。

Input: [[1,4],[4,5]]
Output: [[1,5]]
解釋：區間 [1,4] 與 [4,5] 只接觸邊界，也算重疊。

程式碼

Python 解法

def merge(intervals):
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
last = merged[-1]
if current[0] <= last[1]:
last[1] = max(last[1], current[1])
else:
merged.append(current)
return merged

Java 解法

import java.util.*;
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[0][0];
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
merged.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] last = merged.get(merged.size() - 1);
if (intervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], intervals[i][1]);
} else {
merged.add(intervals[i]);
}
}
return merged.toArray(new int[merged.size()][]);
}
}

Java vs Python 差異
• Python 排序用 sort(key=lambda x: x[0])，Java 用 Arrays.sort 搭配 Comparator
• Python 使用 list 操作，Java 使用 ArrayList 並最後轉成陣列
• 核心邏輯相同：先排序、再遍歷合併重疊區間

複雜度分析
• 時間複雜度：O(n log n)，主要是排序區間
• 空間複雜度：O(n)，最壞情況下所有區間都不重疊，需要存入新集合