56. 合并區間

以數組?intervals?表示若干個區間的集合，其中單個區間為?intervals[i] = [starti, endi]?。請你合并所有重疊的區間，并返回?一個不重疊的區間數組，該數組需恰好覆蓋輸入中的所有區間?。

示例 1：

輸入：intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出：[[1,6],[8,10],[15,18]]
解釋：區間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].

示例?2：

輸入：intervals = [[1,4],[4,5]]
輸出：[[1,5]]
解釋：區間 [1,4] 和 [4,5] 可被視為重疊區間。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

實現步驟

1. 檢查輸入數組是否為空或長度為0，如果是，直接返回空數組。
2. 否則，對intervals數組進行排序。使用Arrays.sort自定義Comparator。
3. 創建merged列表，初始時加入第一個區間。
4. 遍歷從第二個區間開始的所有區間。
5. 獲取merged列表的最后一個區間。
6. 比較當前區間的start和最后一個區間的end。
7. 如果當前區間的start <= 最后一個區間的end，則合并，更新最后一個區間的end為兩者的最大值。
8. 否則，直接將當前區間加入merged列表。
9. 最后，將merged列表轉換為數組返回。

程序代碼

• 排序區間：首先將所有區間按照起始點進行排序。這樣可以確保所有可能重疊的區間都是連續的。
• 合并重疊區間：遍歷排序后的區間，逐個合并重疊的區間。具體來說，維護一個合并后的區間結果列表，如果當前區間與前一個合并后的區間重疊，則合并它們；否則，將當前區間添加到結果列表中。

class Solution {public int[][] merge(int[][] intervals) {// 數組為空（長度為0）if(intervals.length == 0){return new int[0][];}// 按區間的起始點進行排序Arrays.sort(intervals,(a,b) -> Integer.compare(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);int[] current = intervals[i];// 當前區間的起始點小于等于上一個區間的結束點，說明有重疊if(current[0] <= last[1]){// 合并區間，更新結束點為兩者較大的那個last[1] = Math.max(last[1],current[1]);} else{// 無重疊，直接添加當前區間merged.add(current);}}return merged.toArray(new int[merged.size()][]);}
}

補充：使用 Lambda 表達式對區間數組按起始點升序排序

在Java中，Arrays.sort()方法的第二個參數可以接收一個Comparator對象，用于定義排序規則。Lambda表達式在這里的作用是簡化Comparator的匿名內部類的定義，直接描述兩個區間如何比較大小。

Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

解析：

????????Arrays.sort()的作用：對數組intervals進行排序，排序規則由第二個參數（Lambda表達式）決定。

????????Lambda表達式 (a,b) -> ...：

? ? ? ? ? ? ? ??1. a 和 b 是待比較的兩個區間（即intervals中的兩個元素，類型是int[ ]）。

? ? ? ? ? ? ? ? 2. a[0] 和 b[0] 分別表示這兩個區間的起始點。

? ? ? ? ? ? ? ? 3. Integer.compare(a[0]，b[0]）的作用是：比較兩個起始點的大小。

????????比較邏輯：

? ? ? ? ? ? ? ??如果 a[0] < b[0]，返回負數，表示a應該排在b的前面（升序）。

? ? ? ? ? ? ? ? 如果 a[0] > b[0]，返回正數，表示a應該排在b的后面（降序）。

? ? ? ? ? ? ? ? 如果相等，返回0，表示順序不變。

Lambda表達式與傳統寫法的對比：

如果不使用Lambda表達式，代碼需要定義一個匿名的Comparator：

Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] a, int[] b) {return Integer.compare(a[0], b[0]);}
});