Insert Interval (Java)

[LeetCode]

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], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

      This question is very similar with merge intervals. because the intervals is initially sorted according to their start times, so what we should do is just go through every interval in intervals list and put the smaller un-overlap interval into result list and updated current newInterval until to the end. But do not forget to add last newInterval into result list. See code below

	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], insert and merge [4,9] in as [1,2],[3,10],[12,16].
	This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
	/**
	* 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 InsertInterval {
	public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
	ArrayList<Interval> result=new ArrayList<Interval>();
	if (newInterval==null){
	return intervals;
	}
	if (intervals==null||intervals.size()==0){
	result.add(newInterval);
	return result;
	}
	for (Interval temp: intervals){
	if (temp.end<newInterval.start){
	result.add(temp);
	}
	else if (temp.start>newInterval.end){
	result.add(newInterval);
	newInterval=temp;
	}
	else{
	newInterval.start=Math.min(newInterval.start, temp.start);
	newInterval.end=Math.max(newInterval.end, temp.end);
	}
	}
	result.add(newInterval);
	return result;
	}
	}

view raw InsertInterval.java hosted with ❤ by GitHub