[Java]leetcode56 Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

题意是：给定上面的区间范围，然后将区间上有交叉的部分进行融合。这一题需要注意的区间的开始可能不是递增的，也就是有可能[1,2],[4,6],[0,6]的情况。 之前也遇到过这样的题，想着用数组的方式去解题，感觉很复杂，没法下笔。后来看了一下Leetcode上是将每个区间作为一个对象来处理，思路瞬间开阔了很多。那对于每个区间的起始值不是递增情况，我们可以首先对它进行排列。然后再融合。那接下来的合并就有三种情况， 第一种是例如[0,4][1,3]的情况，前面的全部包含后面的。 第二种是例如[0,3][2,6]，部分交叉。 第三种是例如[0,4][5,6]的情况，就是没有交叉。 而第一种和第二种又可以看成一种情况。 下面给出代码：

/** * Definition for an interval. * public class Interval { *int start; *int end; *Interval() { start = 0; end = 0; } *Interval(int s, int e) { start = s; end = e; } * } */{public List<Interval> merge(List<Interval> intervals) {int len=intervals.size();if(len<=1)return intervals;//对intervals进行排序Collections.sort(intervals,new IntervalsComparator());//取intervals中的第一个区间Interval newInterval=intervals.get(0);List<Interval> res=new ArrayList<Interval>();for(int i=1;i<len;i++){Interval interval=intervals.get(i);//不相交的情况if(newInterval.end<interval.start){res.add(newInterval);newInterval=interval;}else{//相交的情况newInterval=new Interval(newInterval.start,Math.max(newInterval.end,interval.end));}}res.add(newInterval);return res;}//自定义排序类，按照Interval的start变量进行升序排序 class IntervalsComparator implements Comparator<Interval>{(Interval i1,Interval i2){return i1.start-i2.start;}}}

这题的关键点是定义了一个newInterval，首先进行排序，，排除出现后面的区间与前面融合区间相交的情况，然后从前到后进行动态的融合。

也许不是自己该去发挥的地方，还是让自己到最适合自己战斗的方面去吧!勇敢的接受自己的失败，