这题思路 不算难，但同样是要注意边界条件， high level的思路是如果新插入的interval没有任何overlap，那就直接插入，否则，就通过如下方式合并：删掉所有的有overlap的interval，再插入一个新的interval
那么问题来了，如何确定哪些是overlap的interval, 新的interval又是从哪儿到哪儿？
要回答这两个问题，通过两次循环遍历足矣，上代码：
/** * 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 int compare(Interval interval, int pos){ if(pos<interval.start){ // point to the left return -1; }else if(pos<=interval.end){ // in the interval return 0; }else{ // point to the right return 1; } } public List<Interval> insert(List<Interval> intervals, Interval newInterval) { int startPos = 0; int endPos = 0; int mergeStart = newInterval.start; int mergeEnd = newInterval.end; boolean rightOverlap = false; int i = 0; for(i = 0 ; i<intervals.size(); i++){ Interval current = intervals.get(i); int comp = compare(current, newInterval.start); if(comp==1){ continue; }else if(comp==0){ startPos = i; mergeStart = current.start; break; }else{ startPos = i; mergeStart = newInterval.start; break; } } // move all the way to the end if(i==intervals.size()){ intervals.add(intervals.size(), newInterval); return intervals; } for(i = 0 ; i<intervals.size(); i++){ Interval current = intervals.get(i); int comp = compare(current, newInterval.end); if(comp==1){ continue; }else if(comp==0){ endPos = i; mergeEnd = current.end; rightOverlap = true; break; }else{ endPos = i; mergeEnd = newInterval.end; break; } } if(i==intervals.size()){ endPos = i; } // has overlap if(rightOverlap){ //delete from startPos to endPos and insert a new interval for(i =0 ; i< endPos-startPos+1; i++){ intervals.remove(startPos); } intervals.add(startPos, new Interval(mergeStart, mergeEnd)); }else{ // delete from startPos to endPos-1 and insert a new interval for(i=0; i<endPos-startPos; i++){ intervals.remove(startPos); } intervals.add(startPos, new Interval(mergeStart, mergeEnd)); } return intervals; } }
