難度：Medium

題目：

以數組?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

Related Topics

• 數組
• 排序

---

重點！！！解題思路

第一步：

明確解題手段：使用排序算法是肯定的了，因為判斷區間是否是交集或者包含關系，需要比較前一個數組的第二個值和后一個數組的第一個值之間的關系，想要不考慮其他情況就這樣比較的話，我們需要先給整個二維數組排序，依據每個數組的第一個值進行排序。?

第二步：

依據每個數組的第一個值進行排序后，就可以依次進行比較，判斷數組中是交集還是包含關系了，具體代碼如下?

源碼+講解：

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0]-o2[0];}});  //排序int[][] res=new int[intervals.length][2];  //結果數組int ind=-1;  //模擬數組真實的大小for (int[] interval : intervals) {if (ind==-1 || interval[0]>res[ind][1]){  //當是第一個數組或者此時數組第一個值大于前一個數組的第二個值，說明數組不相交，之間添加到結果數組就可以res[++ind]=interval;}else{  //要不然就是說明數組相交，那么相交的結果就改變前一個數組的第二個值就可以res[ind][1]=Math.max(interval[1],res[ind][1]);}}return Arrays.copyOf(res,ind+1);  //copyOf方法是將數組的真實大小拷貝到新的數組進行返回，因為如果有交集那么肯定少返回一個，那么數組對應的位置就會是空集，這個方法避免了空集的存在}
}

?運行結果：

如果您還有什么疑問或解答有問題，可在下方評論，我會及時回復。

系列持續更新中，點個訂閱吧，喜歡練習算法那就點個攢吧?