題目描述

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

題目示例

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

解題思路

首先將數(shù)組按照左邊界按照從小到大進(jìn)行排序，目的是為了讓兩個重疊的區(qū)間更容易相鄰在一塊，然后我們定義收集結(jié)果的數(shù)組 merged，并遍歷題目輸入的數(shù)組，按照以下貪心策略解決該題目：

• 取出當(dāng)前遍歷區(qū)間的左邊界和右邊界。
• 如果結(jié)果數(shù)組沒有元素（代表剛開始遍歷第一個）或者當(dāng)前遍歷區(qū)間的左邊界大于結(jié)果數(shù)組最后一個元素的右邊界（表示無重疊部分），直接將當(dāng)前區(qū)間收集到結(jié)果數(shù)組中。
• 否則，代表有重疊部分，更新結(jié)果數(shù)組最后一個元素的右邊界為當(dāng)前遍歷區(qū)間的最大值。
  

參考代碼

class Solution {public int[][] merge(int[][] intervals) {if(intervals.length == 0) return new int[0][2];// 按照左邊界排序，這樣可以使的兩個重疊區(qū)間更容易在一塊Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});// 收集結(jié)果的數(shù)組List<int[]> merged = new ArrayList<int[]>();for(int i = 0; i < intervals.length; i++) {int L = intervals[i][0];int R = intervals[i][1];// 如果結(jié)果數(shù)組沒有元素，或者當(dāng)前元素和上個處理元素?zé)o重疊部分if(merged.size()==0 || merged.get(merged.size()-1)[1] < L) {// 直接可以收集當(dāng)前結(jié)果merged.add(new int[]{L, R});} else {// 如果有重疊部分// 更新上個結(jié)果的右邊界為當(dāng)前右邊界最大值merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], R);}}// 返回結(jié)果數(shù)組return merged.toArray(new int[merged.size()][]);}
}