劍指 Offer II 074合并區間(相關話題：二維資料排序，區間合并)

 題目描述

以數組 ​

​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] 可被視為重疊區間。

解題思路

如果我們按照區間的左端點排序，那麼在排完序的清單中，可以合并的區間一定是連續的。如下圖所示，标記為藍色、黃色和綠色的區間分别可以合并成一個大區間，它們在排完序的清單中是連續的：

我們用數組 merged 存儲最終的答案。

首先，我們将清單中的區間按照左端點升序排序。然後我們将第一個區間加入 merged 數組中，并按順序依次考慮之後的每個區間：

如果目前區間的左端點在數組 merged 中最後一個區間的右端點之後，那麼它們不會重合，我們可以直接将這個區間加入數組 merged 的末尾；

Arrays.sort(intervals, new Comparator<int[]>() {
     public int compare(int[] interval1, int[] interval2) {
           return interval1[0] - interval2[0];
     }
});      

代碼實作 

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}