描述

给出一组区间，请合并所有重叠的区间。

请保证合并后的区间按区间起点升序排列。

数据范围：区间组数 0≤n≤2×105，区间内 的值都满足 0≤val≤2×105

示例1

输入：

[[10,30],[20,60],[80,100],[150,180]]

返回值：

[[10,60],[80,100],[150,180]]

示例2

输入：

[[0,10],[10,20]]

返回值：

[[0,20]]

思路分析：

该题可以使用贪心算法解决，找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

步骤：

1.先把这些区间进行排序，使用 Collections.sort()方法

2.根据前一个区间的end小于当前区间的start，区间不重叠；反之则重叠。

3.将这些区间添加到res里面，最终返回res

代码分析：

java">import java.util.*;/** public class Interval {*   int start;*   int end;*   public Interval(int start, int end) {*     this.start = start;*     this.end = end;*   }* }*/public class Solution {/*** * @param intervals Interval类ArrayList * @return Interval类ArrayList*/public ArrayList<Interval> merge (ArrayList<Interval> intervals) {ArrayList<Interval> res=new ArrayList<>();//特殊情况if(intervals.size()==0) return res;//按区间进行排序Collections.sort(intervals,(o1,o2)->o1.start-o2.start);//把排序后的第一个区间放入resres.add(intervals.get(0));int before=0;for(int i=1;i<intervals.size();i++){Interval o1=intervals.get(i);Interval origin=res.get(before);//区间不重叠，前一个区间的end小于当前区间的startif(origin.end<o1.start){//添加res.add(o1);before++;}else{//区间重叠，前一个区间的end大于当前区间的startres.remove(before);Interval s=new Interval(origin.start,Math.max(origin.end,o1.end));res.add(s);}}return res;}
}