[解题思路]
创建一个新的interval集合，然后每次从旧的里面取一个interval出来，然后插入到新的集合中。
没什么好说的，遍历已有vector，如果当前interval小于newinterval，插入当前；如果当前interval大于newInterval，则插入newInterval及当前；如果两者重叠，merge以后插入新的interval。
实现中之所以重新new了一个vector来存放结果的原因，是不愿意破坏传入参数。
在原有的vector上面直接修改的话，唯一的区别就是，一旦发现当前interval大于newInterval，就应该return了。
/** * 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 class Solution { public ArrayList<Interval> merge(ArrayList<Interval> intervals) { ArrayList<Interval> result = new ArrayList<Interval>(); for(int i =0; i < intervals.size(); i++){ Interval temp = intervals.get(i); result = insert(result, temp); } return result; } public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) { ArrayList<Interval> result = new ArrayList<Interval>(); for(int i = 0; i < intervals.size(); i ++){ Interval temp = intervals.get(i); if(temp.start> newInterval.end){ result.add(newInterval); for(int j = i; j < intervals.size(); j++){ result.add(intervals.get(j)); } return result; } else if( newInterval.start > temp.end){ result.add(temp); continue; } else{ // Attention : method Math.min and Math.max newInterval.start = Math.min(newInterval.start, temp.start); newInterval.end = Math.max(newInterval.end, temp.end); } } /*easy to forget. The situation that newInterval.start is the biggest */ result.add(newInterval); return result; } }
原文：http://www.cnblogs.com/RazerLu/p/3535657.html