给定一个列表，将有重叠部分的合并。例如[ [ 1 3 ] [ 2 6 ] ] 合并成 [ 1 6 ] 。
解法一
常规的思想，将大问题化解成小问题去解决。
假设给了一个大小为 n 的列表，然后我们假设 n - 1 个元素的列表已经完成了全部合并，我们现在要解决的就是剩下的 1 个，怎么加到已经合并完的 n -1 个元素中。
这样的话分下边几种情况， 我们把每个范围叫做一个节点，节点包括左端点和右端点。
- 如下图，新加入的节点左端点和右端点，分别在两个节点之间。这样，我们只要删除这两个节点，并且使用左边节点的左端点，右边的节点的右端点作为一个新节点插入即可。也就是删除 [ 1 6 ] 和 [ 8 12 ] ，加入 [ 1 12 ] 到合并好的列表中。
2.如下图，新加入的节点只有左端点在之前的一个节点之内，这样的话将这个节点删除，使用删除的节点的左端点，新加入的节点的右端点，作为新的节点插入即可。也就是删除 [ 1 6 ]，加入 [ 1 7 ] 到合并好的列表中。
3.如下图，新加入的节点只有右端点在之前的一个节点之内，这样的话将这个节点删除，使用删除的节点的右端点，新加入的节点的左端点，作为新的节点插入即可。也就是删除 [ 8 12 ]，加入 [ 7 12 ] 到合并好的列表中。
如下图，新加入的节点的左端点和右端点在之前的一个节点之内，这样的话新加入的节点舍弃就可以了。
如下图，新加入的节点没有在任何一个节点之内，那么将它直接作为新的节点加入到合并好的节点之内就可以了。
‘如下图，还有一种情况，就是新加入的节点两个端点，将之前的节点囊括其中，这种的话，我们只需要将囊括的节点删除，把新节点加入即可。把 [ 8 12 ] 删除，将 7 13 加入即可。并且，新加入的节点可能会囊括多个旧节点，比如新加入的节点是 [ 1 100 ]，那么下边的三个节点就都包括了，就需要都删除掉。
以上就是所有的情况了，可以开始写代码了。
publicclassInterval { intstart; intend; Interval() { start=0; end=0; } Interval(ints, inte) { start=s; end=e; } } publicList<Interval>merge(List<Interval>intervals) { List<Interval>ans=newArrayList<>(); if (intervals.size() ==0) returnans; //将第一个节点加入，作为合并好的节点列表ans.add(newInterval(intervals.get(0).start, intervals.get(0).end)); //遍历其他的每一个节点for (inti=1; i<intervals.size(); i++) { Intervalstart=null; Intervalend=null; //新加入节点的左端点inti_start=intervals.get(i).start; //新加入节点的右端点inti_end=intervals.get(i).end; intsize=ans.size(); //情况 6，保存囊括的节点，便于删除List<Interval>in=newArrayList<>(); //遍历合并好的每一个节点for (intj=0; j<size; j++) { //找到左端点在哪个节点内if (i_start>=ans.get(j).start&&i_start<=ans.get(j).end) { start=ans.get(j); } //找到右端点在哪个节点内if (i_end>=ans.get(j).start&&i_end<=ans.get(j).end) { end=ans.get(j); } //判断新加入的节点是否囊括当前旧节点，对应情况 6if (i_start<ans.get(j).start&&i_end>ans.get(j).end) { in.add(ans.get(j)); } } //删除囊括的节点if (in.size() !=0) { for (intindex=0; index<in.size(); index++) { ans.remove(in.get(index)); } } //equals 函数作用是在 start 和 end 有且只有一个 null，或者 start 和 end 是同一个节点返回 true，相当于情况 2 3 4 中的一种if (equals(start, end)) { //如果 start 和 end 都不等于 null 就代表情况 4// start 等于 null 的话相当于情况 3ints=start==null?i_start : start.start; // end 等于 null 的话相当于情况 2inte=end==null?i_end : end.end; ans.add(newInterval(s, e)); // start 和 end 不是同一个节点，相当于情况 1 } elseif (start!=null&&end!=null) { ans.add(newInterval(start.start, end.end)); // start 和 end 都为 null，相当于情况 5 和 情况 6 ，加入新节点 }elseif (start==null) { ans.add(newInterval(i_start, i_end)); } //将旧节点删除if (start!=null) { ans.remove(start); } if (end!=null) { ans.remove(end); } } returnans; } privatebooleanequals(Intervalstart, Intervalend) { if (start==null&&end==null) { returnfalse; } if (start==null||end==null) { returntrue; } if (start.start==end.start&&start.end==end.end) { returntrue; } returnfalse; }
时间复杂度：O（n²）。
空间复杂度：O （n），用来存储结果。
总
开始的时候，使用最常用的思路，将大问题化解为小问题，然后用递归或者直接用迭代实现。
