Insert Interval Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]. Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], inser…

InsertInterval.java

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval x) {
    	ArrayList<Interval> list = new ArrayList<Interval>();
    	boolean done = false;
    	Itrator<Interval> iterator = intervals.iterator();
    	while (iterator.hasNext() {
		Interval itv = iterator.next();
		if (done || itv.end < x.start){
			list.add(itv);
		}else if (x.end < itv.start){
			list.add(x);
			list.add(itv);
			done = true;
		}else{
			x.start = Math.min(x.start, itv.start);
			x.end = Math.max(x.end, itv.end);
		}
	}
    	if (!done)
		list.add(x);
	return list;
}