(LeetCode 面试经典 150 题) 56. 合并区间 （排序）

思路：排序，时间复杂度0(nlogn)。

将数组intervals按左区间升序排序即可，然后维护r。细节看注释

C++版本：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {// 按左区间升序排序sort(intervals.begin(),intervals.end());vector<vector<int>> v;// 当前区间int l=intervals[0][0],r=intervals[0][1];for(int i=1;i<intervals.size();i++){// 当前区间和后面的不会有重叠if(r<intervals[i][0]){v.push_back({l,r});l=intervals[i][0];r=intervals[i][1];}else{// 有重叠，维护rr=max(r,intervals[i][1]);}}v.push_back({l,r});return v;}
};

JAVA版本：

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a,b)-> a[0]-b[0]);List<int[]> v= new ArrayList<>();int l=intervals[0][0],r=intervals[0][1];for(int i=1;i<intervals.length;i++){if(r<intervals[i][0]){v.add(new int[]{l,r});l=intervals[i][0];r=intervals[i][1];}else{r=Math.max(r,intervals[i][1]);}}v.add(new int[]{l,r});return v.toArray(new int[v.size()][]);}
}

GO版本：

func merge(intervals [][]int) [][]int {v:=[][]int{}sort.Slice(intervals,func(i,j int) bool{if intervals[i][0]!=intervals[j][0] {return intervals[i][0]<intervals[j][0]}return intervals[i][1]>intervals[j][1]})l,r:=intervals[0][0],intervals[0][1]for i:=0;i<len(intervals);i++ {if r<intervals[i][0] {v=append(v,[]int{l,r})l=intervals[i][0]r=intervals[i][1]}else {r=max(r,intervals[i][1])}}v=append(v,[]int{l,r})return v
}