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].

**Thoughts:**

We insert the new interval into the set of intervals according to their start time. Then we look back (i.e., left) to see if we can merge. Then we look right (i.e., right) to see if we can merge. For Example 2, the algorithm works as:

- Insert [4,9] into original set of intervals according to the start time. So we’ve got: [1,2],[3,5],[4,9],[6,7],[8,10],[12,16] after insertion.
- From [4,9], look back to see if we can merge. [3,5] can be merged with [4,9] so [3,5] will be deleted and we have a updated entry: [3,9]. Afterwards, the list becomes: [1,2],[3,9],[6,7],[8,10],[12,16].
- Continue to look to left. [1,2] cannot be merged with [3,9] so this is done.
- Start to look to the right. [3,9] can be merged with [6,7]. In fact, [3,9] will ‘absorb’ [6,7], so [6,7] will just be deleted. We have: [1,2],[3,9],[8,10],[12,16].
- Continue to look to the right. [3,9] can be merged with [8,10] so [8,10] will be deleted and we have a updated entry [3,10]. The list becomes: [1,2],[3,10],[12,16].
- [3,10] cannot be further merged with [12,16] so the result is just: [1,2],[3,10],[12,16].

**Code (Java):**

public class Solution { public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) { int startIndex = 0; for(int i = -1; i < intervals.size(); ++i) { Interval current = i == -1 ? null : intervals.get(i); Interval next = i + 1 == intervals.size() ? null : intervals.get(i+1); if( (current == null || current.start <= newInterval.start) && (next == null || newInterval.start <= next.start) ) startIndex = i + 1; } ArrayList<Interval> sol = new ArrayList<Interval>(); sol.addAll(intervals); sol.add(startIndex, newInterval); int i = startIndex; // shrink to left for(; i - 1 >= 0;) { Interval current = sol.get(i); Interval previous = sol.get(i - 1); if(current.start <= previous.end) { current.start = current.start >= previous.start ? previous.start : current.start; current.end = current.end >= previous.end? current.end : previous.end; sol.remove(i-1); --i; } else { break; } } for(int j = i; j + 1 < sol.size();) { Interval current = sol.get(j); Interval next = sol.get(j + 1); if(current.end >= next.start) { current.start = current.start >= next.start ? next.start : current.start; current.end = current.end >= next.end ? current.end : next.end; sol.remove(j+1); } else { break; } } return sol; } }

Code (C++)

Thanks for this post.class Solution { public: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { vector<Interval> result; bool isLarge = true; for(vector<Interval>::iterator it = intervals.begin(); it != intervals.end(); ++it) { if(it -> end < newInterval.start) { result.push_back(*it); continue; } if(it -> start > newInterval.end) { if(isLarge) { result.push_back(newInterval); isLarge = false; } result.push_back(*it); continue; } newInterval.start = min(it -> start, newInterval.start); newInterval.end = max(it -> end, newInterval.end); } if(isLarge) result.push_back(newInterval); return result; } };Advertisements