合并区间链接到链接：https://leetcode-cn.com/problems/merge-intervals给定一组区间，请合并所有重叠的区间。示例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]可以被认为是重叠区间.注意：输入类型已于2019年4月15日更改。请重置新方法签名的默认代码定义。Tips：intervals[i][0]<=intervals[i][1]大家应该感受一下。这道题一定要排序，那么到底是按左边界排序还是按右边界排序呢？边界排序，排序后局部最优：每次合并取最大的右边界，这样可以合并更多的区间，整体最优：合并所有重叠的区间。局部最优可以导致全局最优。如果找不到反例，请尝试贪婪。那么有同学问，最大的右边界不应该合并吗？这跟贪婪有什么关系？有时贪婪是常识！哈哈左边界从小到大排序后，如果intervals[i][0]&a,constvector&b){returna[0]>merge(vector>&intervals){vector>result;if(intervals.size()==0)returnresult;sort(intervals.begin(),intervals.end(),cmp);boolflag=false;//标记最后一个区间是否合并intlength=intervals.size();for(inti=1;i>合并（vvector>&intervals){vector>result;if(intervals.size()==0)returnresult;//排序参数使用lamda表达式sort(intervals.begin(),intervals.end(),[](constvector&a,constvector&b){returna[0]=intervals[i][0]){//合并区间result.back()[1]=max(result.back()[1],intervals[i][1]);}else{result.push_back(intervals[i]);}}returnresult;}};时间复杂度：O(nlogn)，有快行空间复杂度：O(1)，一旦你一开始的直觉想不出来，可能就一直想不出来。跟着《代码乱记》刷题的应该都觉得贪心难，真的很难。那我们该怎么办呢？正如我贪心系列的贪心算法开篇所说，这些你应该知道！Greedy没有套路，没有框架，所以各种常规方案需要多接触，多实践，自然会想到。《代码随机记录》将涵盖贪心常见的经典题型，你只需要认真学习和签到即可。其他语言版本JavaclassSolution{publicint[][]merge(int[][]intervals){Listres=newLinkedList<>();Arrays.sort(intervals,(o1,o2)->Integer.compare(o1[0],o2[0]));intstart=intervals[0][0];for(inti=1;iintervals[i-1][1]){res.add(newint[]{start,intervals[i-1][1]});start=intervals[i][0];}else{intervals[i][1]=Math.max(intervals[i][1],intervals[i-1][1]);}}res.add(newint[]{start,intervals[intervals.length-1][1]});returnres.toArray(newint[res.size()][]);}}//版本2classSolution{publicint[][]merge(int[][]intervals){LinkedListres=newLinkedList<>();Arrays.sort(intervals,(o1,o2)->Integer.compare(o1[0],o2[0]));res.add(intervals[0]);for(inti=1;iList[List[int]]:iflen(intervals)==0:returnintervalsintervals.sort(key=lambdax:x[0])result=[]result.append(intervals[0])foriinrange(1,len(intervals)):last=result[-1]iflast[1]>=intervals[i][0]:result[-1]=[last[0],max(last[1],intervals[i][1])]else:result.append(intervals[i])returnresultGofuncmerge(intervals[][]int)[][]int{//先从小到大排序sort.Slice(intervals,func(i,jint)bool{returnintervals[i][0]=intervals[i+1][0]{intervals[i][1]=max(intervals[i][1],intervals[i+1][1])//赋值最大intervals=append(intervals[:i+1],intervals[i+2:]...)i--}}returnintervals}funcmax(a,bint)int{ifa>b{returna}returnb}Javascriptvarmerge=function(intervals){intervals.sort((a,b)=>a[0]-b[0]);letprev=intervals[0]letresult=[]for(leti=0;iprev[1]){result.push(prev)prev=cur}else{prev[1]=Math.max(cur[1],prev[1])}}result.push(prev)returnresult};版本2：左右间隔/***@param{number[][]}intervals*@return{number[][]}*/varmerge=function(intervals){letn=intervals.length;if(n<2)returnintervals;intervals.sort((a,b)=>a[0]-b[0]);letres=[],left=intervals[0][0],right=intervals[0][1];for(leti=1;iright){res.push([left,right]);left=intervals[i][0];right=intervals[i][1];}else{right=Math.max(intervals[i][1],right);}}res.push([left,right]);returnres;};
