leetcode刷題（76）—— 56. 合并區間

給出一個區間的集合，請合并所有重疊的區間。

示例 1:

輸入: [[1,3],[2,6],[8,10],[15,18]]

輸出: [[1,6],[8,10],[15,18]]

解釋: 區間 [1,3] 和 [2,6] 重疊, 将它們合并為 [1,6].

示例 2:

輸入: [[1,4],[4,5]]

輸出: [[1,5]]

解釋: 區間 [1,4] 和 [4,5] 可被視為重疊區間。

方法一：排序

思路

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

算法

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

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

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

否則，它們重合，我們需要用目前區間的右端點更新數組 merged 中最後一個區間的右端點，将其置為二者的較大值。

//56. 合并區間
public class Solution56 {
    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return intervals;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int[][] result = new int[intervals.length][2];
        int currentPos = 0;
        result[0] = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            int leftEdge = intervals[i][0];
            if (leftEdge > result[currentPos][1]) {
                result[++currentPos] = intervals[i];
            } else {
                result[currentPos][1] = Math.max(result[currentPos][1], intervals[i][1]);
            }
        }
        return Arrays.copyOf(result, currentPos + 1);
    }
}           

複制

要點：

1.使用一個新的數組 int[][] result

2.由于 int[][] result 的length是intervals.length，必然有很多無用的部分，為[0][0],是以需要進行拷貝結果

3.Arrays.copyOf(result, currentPos + 1);這裡第二個參數是拷貝的長度，是以需要currentPos + 1，但是如果是空數組會出現角标越界，是以需要前置判斷空數組

if (intervals.length == 0) {
            return intervals;
        }           

複制